并查集学习记录

借助于oj的题目对并查集的进行学习，同时利用c语言将题目进行了实现。
并查集原理介绍
实现题目来源：1.朋友圈问题（本文）
2.畅通工程（杭电oj题目）

C语言实现代码

#include<stdio.h>
#include<string.h>

int pre[40000];
int n, m;
int a, b;
int num[40000];
 
//每个点初始化为只含有自己的集合 
void init(){
    int i;
    for(i = 1; i <= n; i++)
        pre[i] = i;
}
//寻找元素x所在集合的代表元素 
int find(int x){
    //如果x等于了pre[x]的值（即初始化的值）则pre[x]为x的代表元素 
    if(x == pre[x])
        return x;
    //若未不是，则继续向上搜索，找到代表元素，同时将x指向它 
    else
        return pre[x] = find(pre[x]);
}
//集合合并操作，将一个集合的代表元素指向另一个集合的代表元素 
void merge(int x, int y){
    //找到x和y所在集合的代表元素 
    int fx = find(x);
    int fy = find(y);
    //将fx指向fy 
    if(fx != fy)
        pre[fx] = fy;
}

int main(){
    int i;
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        while(m--){
            int k;
            scanf("%d", &k);
            scanf("%d", &a);
            k--;
            while(k--){
                scanf("%d", &b);
                merge(a, b);
            }
        }
        memset(num, 0, sizeof(num));
        for(i = 1; i <= n; i++){
            num[find(i)]++;
        }
        int ans = 0;
        for(i = 1; i <= n; i++){
            if(num[i] > ans)
               ans = num[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}