7-25 朋友圈 (25 分) java 并查集

1. 此题就是并查集，就是根据祖先的（俱乐部）不同，分成了许多小集合，每个小集合可以理解为一个俱乐部，用cnt数组去记录每个集合的孩子数量，找出cnt中某个位置的值最大，那么俱乐部的最大人数就求出来了；
2. 需要注意和上一题的模板题：亲戚，稍微有点变化，此题需要依次合并多个人的关系，上题是一对一对的合并，而这一题，一行多个结点属于一个关系，比如1,2,3为同一集合，那么我们可以直接把1和2连通起来，再把把1和3连通起来，就可以让这一行的关系都连了起来；
3. 在处理哪个部落的人最多是多少的问题，我们知道并查集是根据根节点的不同，分成了许多树，我们可以把每一个俱乐部理解为一棵树，我们可以用一个cnt数组，去记录每个部落（根节点）有几个孩子，然后通过ans来保存最大值即可；
4. java最后一个点超时了，但是可以同样的思路，c++或c跑一遍就可以；

import java.util.Scanner;

public class Main {

    static int[] f = new int[30000 + 5];//f[i]=1表示,i的祖先为1
    //用来表示每个祖先结点有多少个孩子
    static int[] cnt = new int[30000 + 5];//cnt[1]=10表示：1这个祖先结点有十个孩子

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        init(n);//初始化
        //并
        for (int i = 1; i <= m; i++) {
            int k = sc.nextInt();
            int a = sc.nextInt();//第一个结点
            for (int j = 1; j < k; j++) {//让a分别去其他的结点连通，就已经使所有结点连通了起来
                int b = sc.nextInt();
                union(a, b);
            }
        }
        //查
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int temp = find(i);
            cnt[temp]++;
            ans = Math.max(ans, cnt[temp]);//直接在这里找最大值，不用再写一次循环去找cnt中的最大值
        }
        System.out.println(ans);
    }

    //初始化操作，把每个节点的祖先先指向自己
    static void init(int n) {
        for (int i = 1; i <= n; i++) {
            f[i] = i;
        }
    }

    //查——路径压缩
    static int find(int i) {
        if (f[i] == i)
            return i;
        //在递归返回的时候，不断将根节点作为每一个结点的父亲
        return f[i] = find(f[i]);//i的祖先为 查找i的祖先
    }

    //并
    static void union(int i, int j) {
        //查找这两个点的祖先，让他们直接产生联系
        int a = find(i);
        int b = find(j);
        f[a] = f[b];//让a的祖先指向b
        //f[b]=f[a];这样也可以，都行
    }
}