- 前言
- 一、题目描述
- 二、思路
- 三、具体代码
蓝桥杯,2017年国赛,并查集,C++
一、题目描述题目描述:
w 星球的一个种植园,被分成 m×n 个小格子(东西方向 m 行,南北方向 n 列)。每个格子里种了一株合根植物。 这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。 如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入描述:
第一行,两个整数 m,n,用空格分开,表示格子的行数、列数(1≤m,n≤1000)。 接下来一行,一个整数 k (0≤k≤105 ),表示下面还有 k 行数据。 接下来 k 行,每行两个整数 a,b,表示编号为 a 的小格子和编号为 b 的小格子合根了。 格子的编号一行一行,从上到下,从左到右编号。 比如:5×4 的小格子,编号:
行列 | ① | ② | ③ | ④ |
---|---|---|---|---|
① | 1 | 2 | 3 | 4 |
② | 5 | 6 | 7 | 8 |
③ | 9 | 10 | 11 | 12 |
④ | 13 | 14 | 15 | 16 |
⑤ | 17 | 18 | 19 | 20 |
输出描述:
输出植物数量。
输入输出样例:
示例:
输入:
5 4 16 2 3 1 5 5 9 4 8 7 8 9 10 10 11 11 12 10 14 12 16 14 18 17 18 15 19 19 20 9 13 13 17
输出:
5
样例图例如下:
运行限制:
最大运行时间:1s 最大运行内存: 256M二、思路
并查集主要是两个函数,一个是合并函数merge,一个是寻找根节点的函数find,合并函数merge(i,j)就是将 i 的根节点的父节点指向 j 的根节点,例如fa[find(x)]=find(j),然后find函数可以通过递归来最终找到根节点。
三、具体代码#includeusing namespace std; int n,m; int k; int fa[1000000]; int find(int x) //寻找根节点的过程 { if(fa[x]==x) { return fa[x]; } else { fa[x]=find(fa[x]); return fa[x]; } } set q; void merge(int i,int j) //合并函数 { fa[find(i)]=find(j); //一定是将i的根节点的父节点指向j的根节点,代表i和j连根 return; } int main() { cin>>n>>m; cin>>k; int ans=0; int count=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { fa[count]=count; //初始化父节点,父节点是自己 count++; } } int a,b; for(int i=1;i<=k;i++) { cin>>a>>b; merge(a,b); } count=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(fa[count]==count) { ans++; } count++; } } cout<