HDU1232 通畅工程并查集

2012-08-17

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 通畅工程并查集