Java Compressed Path Union Find


  • 0
    public class Solution {
        private int[][] matrix;
        private int[] father;
        private int row;
        private int col;
        private int[] dx = {1, 0, -1, 0};
        private int[] dy = {0, 1, 0, -1};
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> result = new ArrayList<Integer>();
            if (positions.length == 0) {
                return result;
            }
            matrix = new int[m][n];
            row = m;
            col = n;
            father = new int[m * n];
            
            for (int i = 0 ; i < positions.length; i++) {
                int[] current = positions[i];
                int x = current[0];
                int y = current[1];
                matrix[x][y] = 1;
                father[x * n + y] = x * n + y;
                if (result.isEmpty()) {
                    result.add(1);
                } else {
                    result.add(countIsland(result.get(result.size() - 1), x, y));
                }
            }
            
            return result;
        }
        
        private int countIsland(int number, int x, int y) {
            int result = number + 1;
            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
                if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col && matrix[nextX][nextY] == 1) {
                    int father1 = find(x * col + y);
                    int father2 = find(nextX * col + nextY);
                    if (father1 != father2) {
                        father[father1] = father2;
                        result--;
                    }
                }
            }
            return result;
        }
        
        private int find(int x) {
            int parent = father[x];
            while (parent != father[parent]) {
                parent = father[parent];
            }
        
            while (x != father[x]) {
                int next = father[x];
                father[x] = parent;
                x = next;
            }
            
            return parent;
        }
    }
    

Log in to reply
 

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