第九篇 LeetCode Number of Islands II

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<Integer>();
        if (positions == null || positions.length == 0) {
            return result;
        }
        UnionFind uf = new UnionFind(m, n);
        int[] rows = {0, 1, 0, -1};
        int[] cols = {1, 0, -1, 0};
        for (int i = 0; i < positions.length; i++) {
            uf.add(positions[i][0], positions[i][1]);
            for (int j = 0; j < 4; j++) {
                int x1 = positions[i][0] + rows[j];
                int y1 = positions[i][1] + cols[j];
                if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n) {
                    if (uf.isIsland(x1, y1)) {
                        uf.union(positions[i][0], positions[i][1], x1, y1);
                    }
                }
            }
            result.add(uf.getCount());
        }
        return result;
    }
    
    class UnionFind {
        private int count; //number of islands
        private int[] parent;
        private int[] weight;
        private int n;
        
        public UnionFind(int m, int n) {
            this.count = 0;
            this.n = n;
            this.parent = new int[m * n];
            this.weight = new int[m * n];
            for (int i = 0; i < m * n; i++) {
                parent[i] = -1;
                weight[i] = 0;
            }
        }
        
        public void union(int x0, int y0, int x1, int y1) {
            int idx0 = getIndex(x0, y0);
            int idx1 = getIndex(x1, y1);
            int root0 = find(idx0);
            int root1 = find(idx1);
            if (root0 == root1) {
                return;
            }
            if (weight[root0] > weight[root1]) {
                parent[root1] = root0;
            } else if (weight[root0] < weight[root1]) {
                parent[root0] = root1;
            } else {
                parent[root1] = root0;
                weight[root0]++;
            }
            count--;
        }
        
        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }
        
        public int getCount() {
            return count;
        }
        
        public void add(int x, int y) {
            int idx = getIndex(x, y);
            parent[idx] = idx;
            weight[idx] = 1;
            count++;
        }
        
        public boolean isIsland(int x, int y) {
            int idx = getIndex(x, y);
            return parent[idx] != -1;
        }
        
        private int getIndex(int x, int y) {
            return x * n + y;
        }
        
    }
}