本文共 1085 字，大约阅读时间需要 3 分钟。

题意

总共n个人，有m组（一个人可能在多个组里，也可能一个都不在），如果一个知道新闻就会告诉他所在的组里的人，然后组里的其他人继续传播；任务是假设第i个人知道新闻，问最终多少人知道新闻（输出n个整数（i从1~n））

思路

这题明显用并查集，然后用个数组记录人数，不过我是直接用set把数塞进去，输出大小，注意最后要在从1~n跑一遍find把根节点统一了才能开始塞数进set

并查集

int find(int k){
   	if(r[k] == k) return k;	return r[k] = find(r[k]);}void merge(int a, int b){
   	int fa = find(a);	int fb = find(b);	if(fa != fb) r[fb] = fa;}

代码

#include 
   
    using namespace std;typedef long long ll;int r[500100];set
    
      s[500100];int find(int k){
   	if(r[k] == k) return k;	return r[k] = find(r[k]);}void merge(int a, int b){
   	int fa = find(a);	int fb = find(b);	if(fa != fb) r[fb] = fa;}int main(){
   	int n, m;	scanf("%d%d", &n, &m);	for(int i = 1; i <= n; i++){
   		r[i] = i;	}	while(m--){
   		int t, temp, pos;		scanf("%d", &t);		for(int i = 0; i < t; i++){
   			scanf("%d", &temp);			if(i == 0){
   				pos = temp;			}			else{
   				merge(pos, temp);			}		}	}	for(int i = 1; i <= n; i++){
   		find(i);	}	for(int i = 1; i <= n; i++){
   		s[r[i]].insert(i);	}	for(int i = 1; i <= n; i++){
   		cout << s[r[i]].size() << " ";	}	cout << endl;}