并查集

QuickUnion

class QuickUnion {
    Integer[] arr;
    public QuickUnion(int size) {
        this.arr = new Integer[size];
        for (int i = 1; i < arr.length; i++)
            arr[i] = new Integer(i);
    }
    public int findRoot(int i) {
        while (i != arr[i]) i = arr[i];
        return i;
    }
    public void union(int a, int b) {
        a = findRoot(a);
        b = findRoot(b);
        arr[a] = b;
    }
}

加权QucikUnion

class QuickUnion {
    private int[] arr;
    private int[] sz;
    public QuickUnion(int size) {
        this.arr = new int[size];
        this.sz = new int[size];
        for (int i = 0; i < arr.length; i++){
            arr[i] = i;
            sz[i] = 1;
        }
    }
    public int findRoot(int i) {
        int count = 0;
        while (i != arr[i]) {
            i = arr[i];
            count++;
        }
        System.out.println("访问次数:"+count);
        return i;
    }
    public void union(int a, int b) {
        a = findRoot(a);
        System.out.println("内容:"+a);
        b = findRoot(b);
        System.out.println("内容:"+b);

        if (a == b) return;
        if (sz[a] > sz[b]) {
            arr[b] = a;
            sz[a] += sz[b];
        } else {
            arr[a] = b;
            sz[b] += sz[a];
        }
    }
}