HDU 1232 -畅通工程(并查集）
题目
http://acm.hdu.edu.cn/showproblem.php?pid=1232
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1e3 + 100;
int pre[MAXN],a[MAXN];
int find(int x)
{
if(pre[x]==x) return x;
return pre[x]=find(pre[x]);
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy) pre[fy]=fx;
}
int main()
{
int n,i,k;
long long a,b,m;
while(cin>>n)
{
if(n==0) break;
cin>>m;
for(i=1;i<=n;i++)
pre[i]=i;
while(m--)
{
cin>>a>>b;
join(a,b);
}
long long ans=0;
for(i=1;i<=n;i++)
{
if(pre[i]==i) ans++;//如果一个数（城镇）的父节点是它本身，则说明与其他路不通
}
cout<<ans-1<<endl;
}
return 0;
}
