题目链接：

---

题意：大概就是分成几个小团体，给每个人用1 - n编号，当对某个人传播消息的时候，整个小团体就知道这个消息，输出 分别对1 - n编号的某个人传递消息时，有多少人知道这个消息。

思路：题目可理解为输出1 - n每个号码所在团体总人数，利用并查集不断向集合添加成员，记录每个集合的人数，保存在根节点的sum[]中，查询每个节点的根节点，输出根节点sum[]；

总结：初看好像是简单并查集，于是敲了个模板上去果断TLE！orz脑子抽了写了个O_(n²)的算法，后面优化了一下就过了。

AC代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn = 5e5 + 5; 5 int far[maxn]; 6 //int Rank[maxn]; 7 int sum[maxn]; 8 int n,m; 9 int find(int x)10 {11     if(far[x] == x)return x;12     else return far[x] = find(far[x]);13 }14 bool check(int x,int y)15 {16     return find(x) == find(y);17 }18 void unite(int x,int y)19 {20     x = find(x);21     y = find(y);22     if(x == y)return;23     far[y] = x;24     sum[x] += sum[y];//集合的合并25    /* if(Rank[x] > Rank[y]) far[y] = x;26     else27     {28         far[x] = y;29         if(Rank[y] == Rank[x]) Rank[y]++;30     }*/31 }32 void init(int n)33 {34     for(int i = 0;i <= n;i++)35     {36         far[i] = i;37         //Rank[i] = 0;38         sum[i] = 1;39     }40 }41 int main()42 {43     while(~scanf("%d%d",&n,&m))44     {45         init(n);46         int t;47         int a,b;48         while(m--)49         {50             scanf("%d",&t);51             if(t >= 1)52             {53                 scanf("%d",&a);54                 for(int i = 1;i < t;i++)55                 {56                     scanf("%d",&b);57                     if(!check(a,b) )58                     {59                         unite(a,b);60                     }61                 }62             }63         }64         for(int i = 1;i <= n;i++)65         {66             int x = find(i);67             printf("%d ",sum[x]);68         }69         printf("\n");70     }71     return 0;72 }