文章
18
粉丝
0
获赞
106
访问
5.4k
#include<stdio.h>
int father [1005]={0};
int num[1005]={0};//标记出现过的节点
int find(int x)
{
if(x==father[x]) return x;
father[x] = find(father[x]);
return father[x];
}
void Init(void)
{
for(int i=1;i<=1000;i++)
{
father[i] = i;
}
}
int main()
{
int i,j;
int cnt=0;
Init();
while(scanf("%d %d",&i,&j)!=EOF)
{
if(i==j)//自己就是自己的根节点,标记一下出现了退出
{
num[i] = 1;
continue;
}
int fi = find(i);
int fj = find(j);
if(fi!=fj)
{
father[fi] = fj;
num[i] = 1;
num[j] = 1;
}
}
int vis[1000]={0};//根节点是否标记过了
for(int i=1;i<=1000;i++)
{
if(num[i])//出现过的节点
{
int root = find(i);
if(!vis[root])//没有标记过的根节点就+1
{
vis[root]=1;
cnt++;
}
}
}
printf("%d\n",cnt);
return 0;
}
登录后发布评论
暂无评论,来抢沙发