[蓝桥杯 2017 国 C] 合根植物
题目描述
w 星球的一个种植园,被分成 m × n m \times n m×n 个小格子(东西方向 m m m 行,南北方向 n n n 列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入格式
第一行,两个整数 m m m, n n n,用空格分开,表示格子的行数、列数( 1 < m , n < 1000 1<m,n<1000 1<m,n<1000)。
接下来一行,一个整数 k k k,表示下面还有 k k k 行数据 ( 0 < k < 1 0 5 ) (0<k<10^5) (0<k<105)。
接下来 k k k 行,每行两个整数 a a a, b b b,表示编号为 a a a 的小格子和编号为 b b b 的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如: 5 × 4 5 \times 4 5×4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
输出格式
一行一个整数,表示答案
样例 #1
样例输入 #1
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
样例输出 #1
5
提示
样例解释
时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
考查知识点:并查集
本题解题关键:
找到多少珠合根植物=找到根的数目 也就是: fa[i]==i
初始化:
void init(int n)
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
查找:
int find(int i)
{
if(i==fa[i])
return i;
else
return fa[i]=find(fa[i]);
}
合并:
void unio(int x,int y)
{
int x_1=find(x);
int y_1=find(y);
if(x_1!=y_1)
fa[x_1]=y_1;
}
在这定义函数不能用union:它是关键字
完整代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000001;
int fa[N];
void init(int n)
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
int find(int i)
{
if(i==fa[i])
return i;
else
return fa[i]=find(fa[i]);
}
void unio(int x,int y)
{
int x_1=find(x);
int y_1=find(y);
if(x_1!=y_1)
fa[x_1]=y_1;
}
signed main()
{
int m,n;
cin>>m>>n;
int w=m*n;
init(w);
int k;
cin>>k;
int o,p;
int ans=0;
for(int i=1;i<=k;i++)
{
cin>>o>>p;
unio(o,p);
}
for(int i=1;i<=w;i++)
{
if(fa[i]==i)
ans++;
}
cout<<ans;
return 0;
}