枣树

灯神讲的比较透彻，详情参考https://www.bilibili.com/video/BV13t411v7Fs

public class UnionFind {
    private int v = 6;
    private int[] parent = new int[6];
    private int[] rank = new int[6];

    public void unionSet(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if(xRoot == yRoot) {//如果两个顶点的根相同，说明在同一颗树中。
            System.out.println(String.format("cycle detected with edge (%d, %d)", x, y) );
            return;
        }
        if(rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;
        }else if (rank[xRoot] < rank[yRoot]){
            parent[xRoot] = yRoot;
        }else {
            parent[xRoot] = yRoot;
            rank[xRoot]++;
        }
    }

    public int find(int n) {
        int root = n;
        while (parent[root] != -1) {
            root = parent[root];
        }
        return root;
    }

    public int[][] test1() {
        return new int[][] {
                {0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}
        };
    }

    public int[][] test2() {
        return new int[][] {
                {0, 1}, {1, 2}, {1, 3}, {3, 4}, {2, 5}, {2, 3}
        };
    }

    public void run(int[][] test) {
        for (int i = 0; i < v; i++) {
            parent[i] = -1;
            rank[i] = 0;
        }
        for (int[] ints : test) {
            int x = ints[0];
            int y = ints[1];
            this.unionSet(x, y);
        }
    }

}