题解 | #朋友圈#

题目的做法就是考察并查集，由于数据量较大，直接查询父节点会超时，需要在find中加上路径压缩，就是将将id数组从父节点改为祖父节点，这样更快
在union过程中，将小树向大树合并与将矮树向高树合并差不多，我用的是后者

import java.util.Scanner;
//题目的做法是实现一个并查集
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = sc.nextInt();
        sc.nextLine();
        while (times > 0) {
            int n = sc.nextInt();
            sc.nextLine();
            UnionFind uf = new UnionFind(10000001);
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                uf.union(a,b);
                sc.nextLine();
            }
            int max = 1;
            for (int i = 0; i < uf.nodeNum.length; i++) {
                max = Math.max(max,uf.nodeNum[i]);
            }
            System.out.println(max);
            times--;
        }
    }

    static class UnionFind {

        //表示当前节点的父节点
        int[] id;
        //表示当前节点为根的那一组的节点数目
        int[] nodeNum;
        //表示当前节点为根的那一组的节点树高度
        int[] height;
        //表示连通集的数目
        int num;

        public UnionFind(int n) {
            num = n;
            id = new int[n];
            nodeNum = new int[n];
            height = new int[n];
            //初始化过程
            //父节点为自己
            //自己为根的高度为1，那一组数目也为1
            for (int i = 0; i < n; i++) {
                id[i] = i;
                nodeNum[i] = 1;
                height[i] = 1;
            }
        }

        //找到当前节点的根节点
        public int find(int p) {
            //如果自己不是根，向上找
            while (p != id[p]) {
                id[p] = id[id[p]];
                p = id[p];
            }
            return p;
        }

        public void union(int p,int q){
            //将较矮的一组树向较高的一组进行合并
            int i = find(p);
            int j = find(q);
            if(i!=j){
                int hp = height[p];
                int hq = height[q];
                if(hp>hq){
                    //如果第一棵树较高，将第二棵树合并为第一棵树的子树
                    id[j] = i;
                    nodeNum[i] += nodeNum[j];
                }else if(hp<hq){
                    //如果第二棵树较高，将第一棵树向第二棵树合并
                    id[i] = j;
                    nodeNum[j] += nodeNum[i];
                }else{
                    //否则，将第一棵树向第二棵树合并
                    id[i] = j;
                    nodeNum[j] += nodeNum[i];
                    height[j] ++;
                }
                num--;
            }
        }
    }
}