文章

18

粉丝

0

获赞

106

访问

4.3k

头像
图的连通分支数 题解:并查集
P1456 上海交通大学机试题
发布于2026年3月18日 10:23
阅读数 494

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发