首页 > 代码库 > hdu 1232
hdu 1232
并查集 入门题
1 #include<cstdio> 2 #include<memory.h> 3 int par[1000]; 4 int Find(int x) 5 { 6 while(par[x] > 0) 7 x = par[x]; 8 return x; 9 }10 void Merge(int x,int y)11 {12 int a,b;13 int tmp;14 a = Find(x);15 b = Find(y);16 if(a != b)17 {18 tmp = par[a] + par[b];19 if(par[a] < par[b]) //a 结点数多于 b的20 {21 par[b] = a;22 par[a] = tmp;23 }24 else25 {26 par[a] = b;27 par[b] = tmp;28 }29 }30 }31 int main()32 {33 freopen("input.txt","r",stdin);34 int x,y,n,m;35 int cnt;36 while(scanf("%d",&n) && n)37 {38 cnt = -1;39 scanf("%d",&m);40 memset(par,-1,sizeof(par));41 while(m--)42 {43 scanf("%d%d",&x,&y);44 Merge(x,y);45 }46 for(int i = 1; i <= n; i++)47 {48 if(par[i] <= -1) cnt++;49 }50 printf("%d\n",cnt);51 }52 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。