首页 > 代码库 > HDU-1232-畅通工程(并查集)

HDU-1232-畅通工程(并查集)

题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1232
考察并查集,(最小生成树)题目很简单
用k记录树根的个数,k-1就是还需要建设的路

#include<iostream>#include<cstdio>
using namespace std;struct node{ int x,y;}s[1005];int father[1005];int Find(int x){ if(x==father[x]) return x; father[x]=Find(father[x]); return father[x];}void Union(int x,int y){ x=Find(x); y=Find(y); if(x!=y) { father[x]=y; }}int main(void){ int n,m,i,j,k,l; while(scanf("%d",&n)==1&&n) { scanf("%d",&m); for(i=0;i<m;i++) scanf("%d%d",&s[i].x,&s[i].y); for(i=1;i<=n;i++) father[i]=i; for(i=0;i<m;i++) { Union(s[i].x,s[i].y); } k=0; for(i=1;i<=n;i++) { if(i==father[i]) k++; } printf("%d\n",k-1); } return 0;}

HDU-1232-畅通工程(并查集)