Union-Find java


  • 0
    C
    public class Solution {
        class UnionFind {
            int[] parent;
            int count;
            int rows, cols;
    
            UnionFind(int m, int n) {
                parent = new int[n*m];
                count = 0;
                rows = m;
                cols = n;
            }
    
            public void set(int i, int j) {
                int index = i*cols + j;
                parent[index] = index;
                count++;
            }
    
            public void union(int index1, int index2) {
                int p1 = find(index1);
                int p2 = find(index2);
                if (p1 != p2) {
                    parent[p1] = p2;
                    count--;
                }
            }
    
            public int find(int index) {
                if(parent[index] == index) return index;
                // path compression
                parent[index] = find(parent[index]);
                return parent[index];
            }
    
            public int getCount() {
                return count;
            }
        }
    
        int[][] neighbors = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> res = new ArrayList<Integer>();
            int[][] grid = new int[m][n];
            UnionFind uf = new UnionFind(m, n);
    
            for(int[] pos : positions) {
                int x = pos[0];
                int y = pos[1];
    
                grid[x][y] = 1;
                uf.set(x, y);
    
                for(int[] nb : neighbors) {
                    int p = x + nb[0];
                    int q = y + nb[1];
    
                    if(p>=0 && p<m && q>=0 && q<n && grid[p][q] == 1) uf.union(x*n + y, p*n + q);
                }
                res.add(uf.getCount());
            }
    
            return res;
        }
    }
    
    

Log in to reply
 

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