畅通工程 杭电oj1863 并查集实现

题目描述：
某省调查诚城镇交通情况，得到现有城镇道路统计表，表中列出了每条道路直接联通的城镇，省政府“畅通计划”的目标是使任意两个城镇之间都可以实现交通。（不一定市直达）问最少需要建设多少条路？
分析：
可以将每一个城镇看作是一个结点，将有路相连的城镇看作是一棵小树，问题的描述就可以转化为如何将所有的小树归并为一棵大树。
此处用到并查集的查找和合并功能:
查找：

int findx(int x)
{
	int i;
	int r=x;
	while(bin[r]!=r)
	{
		r=bin[r];
		return r;
	}
}

将每个数组元素里面内容为自己的直属领导，这样子的话就可以一层一层查到老大；
合并：

int merge(int x,int y)
{	if(x!=y)//x,y分别为树的根节点，类似于老大；要想合并两个集合，只需要将两个老大进行统一即可
	{
		bin[x]=y;
	}
}

代码：

#include<stdio.h>
int bin[10000];
int findx(int x)//实现查找功能，找到某元素的老大
{
	int i;
	int r=x;
	while(bin[r]!=r)
	{
		r=bin[r];
		return r;
	}
}
int merge(int x,int y)//实现合并功能，如果两个城镇之间有路，则合并成一个集合，一个做子节点，一个做根
{
	int fx,fy,t;
	fx=findx(x);
	fy=findx(y);
	if(fx!=fy)
	{
		bin[x]=fy;
	}
}
int main()
{
	
	int n,m,i,x,y,count;
	while(scanf("%d",&n),n)//读入城镇个数
	{
		for(i=1;i<=n;i++)
		{
			bin[i]=i;//起初假设每个都是老大，并没有路，每个集合都是一个数
		}
		for(scanf("%d",&m);m>0;m--)//提供几组有路的城市
		{
			scanf("%d %d",&x,&y);//读入有路的两个城镇
			merge(x,y);//合并城镇，将两个城镇合并为一个小树
			for(count=-1,i=1;i<=n;i++)//遍历数组中有几个老大，count为最少需要建立的路
			//做老大的条件：必须为bin[i]=i;其实老大就是根节点，初始化count是-1，
		    //eg:如果有两个老大，只需要建立一条路
			{
				if(bin[i]==i)当老大的条件
				count++;
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

文章来源: blog.csdn.net，作者：花花叔叔，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_52077949/article/details/114678632