【题解】合根植物
【题目描述】
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
【输入描述】
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第2+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
【题目分析】
【参考答案】
#include<iostream>
using namespace std;
const int MAX=1000010; //数组的最大长度（即图中点个数的最大值）
int m,n; //当前图的长宽规格
int p[MAX]; //用于存放每个点的根节点
//寻找根节点函数
int find(int x)
{
if(p[x]==x) return x;
return p[x]=find(p[x]);
}
//合并函数
void merge(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
p[fx]=fy;
}
int main()
{
int x,y,line;
cin>>m>>n>>line;
//初始化
for(int i=1;i<=n*m;i++)
p[i]=i;
//合并
for(int i=0;i<line;i++)
{
cin>>x>>y;
merge(x,y);
}
int ans=0,a[MAX]={0};
for(int i=1;i<=m*n;i++)
a[find(i)]=1;
for(int i=1;i<=m*n;i++)
if(a[i]) ans++;
cout<<ans<<endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。