HDU1232 通畅工程并查集

HDU1232 畅通工程并查集

这题是并查集的简单运用。我所利用的并查集没有经过优化。只用到了初始化（每个元素都是一个集合）、查找（某个

元素所在的集合，集合以根节点标志）、合并（两集合不属于同一集合则合并）

这题的主要思想在于：找出连通分量的个数。减一之后就是所求最小需要添加的路径数。而利用并查集时可以发现连通

分量的个数等于父节点为自身的节点数目。

AC代码：

#include<iostream>
using namespace std;

const int MAX=1000;
int father[MAX];

void initial(int n)    //初始化
{
	for(int i=1;i<=n;i++)
		father[i]=i;
}

int find(int x)    //查找
{
	while(father[x]!=x)
		x=father[x];

	return x;
}

void combine(int a,int b)   //合并
{
	int tmpa=find(a);
	int tmpb=find(b);

	if(tmpa!=tmpb)
		father[tmpa]=tmpb;
}

int main()
{
	int i,n,m,a,b,tmp;

	while(cin>>n,n)
	{
		initial(n);

		cin>>m;

		for(i=1;i<=m;i++)
		{
			cin>>a>>b;
			combine(a,b);
		}

		tmp=0;
		for(i=1;i<=n;i++)   //确定连通分量个数
		{
			if(father[i]==i)
				tmp++;
		}

		cout<<tmp-1<<endl;
	}

	return 0;
}

HDU1232 通畅工程 并查集

相关推荐

HDU1232 通畅工程并查集