并查集实现

原理

• 划分类别

代码实现

• 路径压缩
• 秩优化

public class UnionFind {
    private int size;

    private int[] array;

    private int[] count;

    public UnionFind(int size) {
        this.size = size;
        array = new int[size];
        count = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = i;
            count[i] = 1;
        }
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (count[rootX] >= count[rootY]) {
            array[rootY] = rootX;
            count[rootX] += count[rootY];
        } else {
            array[rootX] = rootY;
            count[rootY] += count[rootX];
        }
        size--;
    }

    public int find(int index) {
        while (array[index] != index) {
            array[index] = array[array[index]];
            index = array[index];
        }
        return index;
    }

    public int getSize() {
        return size;
    }
}

代表题型

leetcode 547 朋友圈

public class UnionFind {
    private int size;

    private int[] array;

    private int[] count;

    public UnionFind(int size) {
        this.size = size;
        array = new int[size];
        count = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = i;
            count[i] = 1;
        }
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (count[rootX] >= count[rootY]) {
            array[rootY] = rootX;
            count[rootX] += count[rootY];
        } else {
            array[rootX] = rootY;
            count[rootY] += count[rootX];
        }
        size--;
    }

    public int find(int index) {
        while (array[index] != index) {
            array[index] = array[array[index]];
            index = array[index];
        }
        return index;
    }

    public int getSize() {
        return size;
    }
}

class Solution {
    public int findCircleNum(int[][] M) {
        int col = M.length;
        if (col == 0) {
            return 0;
        }
        UnionFind uf = new UnionFind(col);
        for (int i = 0; i < col; i++) {
            for (int j = (i + 1); j < col; j++) {
                if (M[i][j] == 1) {
                    uf.merge(i, j);
                }
            }
        }
        return uf.getSize();
    }
}

leetcode 765 情侣牵手

class UnionFind {
    private int size;

    private int[] array;

    private int[] count;

    public UnionFind(int size) {
        this.size = size;
        count = new int[size];
        array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = i;
            count[i] = 1;
        }
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (count[rootX] >= count[rootY]) {
            array[rootY] = rootX;
            count[rootX] += count[rootY];
        } else {
            array[rootX] = rootY;
            count[rootY] += count[rootX];
        }
        size--;
    }

    public int find(int index) {
        while (array[index] != index) {
            array[index] = array[array[index]];
            index = array[index];
        }
        return index;
    }

    public int getSize() {
        return size;
    }
}


class Solution {
    public int minSwapsCouples(int[] row) {
        int size = row.length / 2;
        UnionFind uf = new UnionFind(size);
        for (int i = 0; i < row.length; i = i + 2) {
            int val1 = row[i] / 2;
            int val2 = row[i + 1] / 2;
            uf.merge(val1, val2);
        }
        return size - uf.getSize();
    }
}

leetcode 200 岛屿数量

class UnionFind {
    public int getSize() {
        return size;
    }

    private int size;

    private int[] count;

    private int[] array;

    public UnionFind(int size) {
        this.size = size;
        count = new int[size];
        array = new int[size];
        for (int i = 0; i < size; i++) {
            count[i] = 1;
            array[i] = i;
        }
    }

    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (count[rootX] >= rootY) {
            array[rootY] = rootX;
            count[rootX] += count[rootY];
        } else {
            array[rootX] = rootY;
            count[rootY] += count[rootX];
        }
        size--;
        return;
    }

    public int find(int index) {
        while (array[index] != index) {
            array[index] = array[array[index]];
            index = array[index];
        }
        return index;
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col;
        UnionFind uf = new UnionFind(size);
        int zeroNum = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    zeroNum++;
                } else {
                    if ((i + 1) < row && grid[i + 1][j] == '1') {
                        uf.merge(i * col + j, (i + 1) * col + j);
                    }
                    if ((j + 1) < col && grid[i][j + 1] == '1') {
                        uf.merge(i * col + j, i * col + j + 1);
                    }
                }
            }
        }
        return uf.getSize() - zeroNum;
    }
}