首页 > 代码库 > 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-畅通工程(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。