并查集——传新闻
在社交网络中，有 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]数组，在添加节点的时候再具体判断情况。