并查集——传新闻

在社交网络中，有 n 个用户在 m 个朋友群中相互交流。我们来分析一下在用户之间传播一些新闻的过程。

最初，某个编号为 x 的用户收到新闻，随后他将新闻发送给他的朋友（如果两个人同属于一个或多个朋友群，则两者便是朋友）。而朋友们继续向他们的朋友发送新闻，以此类推，直至所有人都将新闻告诉了他们的朋友。

对于每个编号为 x 的用户，若最初只有用户 x 开始传播新闻，那么最终知道该新闻的用户数量是多少。

Input

第一行包含两个整数 n, m（ 1 ≤ n, m ≤ 5*10^5 ），分别表示用户和朋友群的数量。

接着是 m 行朋友群的用户情况，第 m_i 行的第1个整数 k 表明该朋友群的用户数量，接下来的 k 个整数表明属于第 m_i 朋友圈的用户编号。

数据量较大，请使用scanf和printf。

Output

输出 n 个整数，表明第 n_i 个用户作为新闻传播者所能传播多少人。

Example

Input

7 5

3 2 5 4

0

2 1 2

1 1

2 6 7

Output

4 4 1 4 4 2 2

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500010
int fa[MAXN],d[MAXN];
void init(int n){
	for(int i=1;i<=n;i++){
		fa[i] = i;
		d[i]=0; 	}
}
int find(int x){
	if(x == fa[x])
		return x;
	else{
		fa[x] = find(fa[x]);
		return fa[x];
	}
}
void unionn(int i,int j){
	int i_fa = find(i);
	int j_fa = find(j);
	if(i_fa==j_fa) return;
	if(d[i_fa]<d[j_fa]) fa[i_fa]=j_fa;//如果后者比前者深，则前者拥有后者所有
	else{
		fa[j_fa]=i_fa;
		if(d[i_fa]==d[j_fa]) d[i_fa]++;//如果一样深，则前者比后者深度多加一个点
	}
}
int n,m,k,m_1,m_i,n_i[MAXN],ans;
int main(){
	scanf("%d""%d",&n,&m);
	init(n);
	while(m--){
		scanf("%d",&k);
		if(!k) continue;
		scanf("%d",&m_1);
		for(int i=1;i<k;i++){ 
			scanf("%d",&m_i);
			unionn(m_1,m_i);
		}					
	}
	for(int i=1;i<=n;i++){
		n_i[find(i)]++;
	} 
	for(int i=1;i<=n;i++){
		printf("%d ",n_i[find(i)]);
	}
	return 0;
}

此题是在正常并查集的每一个结点上求出最深深度，也就是每个结点存储的不再是祖节点，而是祖结点的深度，始化多了一个d[n]数组，在添加节点的时候再具体判断情况。