Short Java Union Find


  • 0
    M
        private class UnionFind {
            int[] p;
            int cnt;
            public UnionFind(int size) {
                p = new int[size];
                cnt = 0;
            }
            public int find(int x) {
                if (p[x] == x) return x;
                return p[x] = find(p[x]);
            }
            public void union(int a, int b) {
                int rootA = find(a);
                int rootB = find(b);
                if (rootA != rootB) {
                    --cnt;
                    p[rootA] = rootB;
                }
            }
            public void add(int x) {
                p[x] = x;
                ++cnt;
            }
        }
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> list = new ArrayList<>();
            final int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
            UnionFind uf = new UnionFind(m * n);
            boolean[][] lands = new boolean[m][n];
            for (int i = 0; i < positions.length; ++i) {
                int x0 = positions[i][0], y0 = positions[i][1];
                lands[x0][y0] = true;
                int z = x0 * n + y0;
                uf.add(z);
                for (int k = 0; k < dx.length; ++k) {
                    int x = x0 + dx[k], y = y0 + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && lands[x][y]) uf.union(z, x * n + y);
                }
                list.add(uf.cnt);
            }
            return list;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.