并查集按秩合并 -电脑资料

   

1239: 中山学院 ACM小组

Time Limit: 1 Sec Memory Limit: 64 MB

    Submit: 79 Solved: 21

    [Submit][Status][Web Board]

Description

经过几年的发展，中山学院 ACM队伍越来越庞大，水平越来越高，影响力也越来越大，

并查集按秩合并

。随着人员数量的壮大，为了营造一个良好的队内之间沟通讨论氛围，教练组决定让队员之间以小组的形式进行讨论。而教练组又希望所有认识的人都在同一组里面讨论，以提高大家的积极性。而这里的认识可以是直接认识或是间接认识（如果A和 B认识，B 和 C认识，这时A和C可以通过B从而使三个人成为同一个小组的成员。四个人以上的做类似的处理。），假如有一个人他谁都不认识，那么没办法了，他只能自己呆在角落发呆了。当然，他自己也算一个讨论组。同时每个队员都有一个唯一的编号，编号从0 到 n-1（n是队员总数）。现在队伍里面有n个人，跟m组关系，每组关系有两个数a，b，表示a跟b相互认识。那么现在问你，我们学校ACM队伍里面一共组成了多少个讨论组？并且对于每个队员，你是否知道他所属讨论组的人数有多少？

Input

对于每组输入，第一行为两个数n 和 m, （1 <=n <=100,1 <=m<=100）,分别代表ACM队内的总人数n和m组关系。接下来的m行，每行有两个数 a 和b，a 和b 是队员的编号，表示 a 和 b认识(0 <= a,b<=n-1)。下面一行输入一个整数k，代表有k组询问，后面的k行每行输入一整数 x，表示此次询问编号为x 的队员所属小组的人数。 （n 和m同时为0时输入结束）

Output

第一行输出讨论小组的数目(格式为”X groups in Zsc_Acmer Camp”，其中X表示讨论小组数目)后面的k行，每一行输出对应询问的回答，

电脑资料

《并查集按秩合并》(https://www.unjs.com)。

Sample Input

5 30 11 20 2501234

Sample Output

3 groups in Zsc_Acmer Camp33311

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int d[500],s[500];int find(int x){    int k,j,r;    r=x;    while(r!=d[r])        r=d[r];    k=x;    while(k!=r)    {        j=d[k];        d[k]=r;        k=j;    }    return r;}void unio(int x,int y){    x=find(x);    y=find(y);    if(x==y)        return ;    if(s[x]>=s[y])    {        d[y]=x;        s[x]+=s[y];    }    else    {        d[x]=y;        s[y]+=s[x];    }}int main(){    int n,m,a,b,ki,tt;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0)            break;        for(int i=0;i<n;i++) aa="find(tt);" cas="0;" d="" groups="" i="0;i<n;i++)" in="" int="" pre="" return="" zsc_acmer=""></n;i++)></cstring></cstdio></iostream>