Union-Find Set in Java


  • 0
    C
    class UnionFindSet {
    
    	int[] nodes;
    	boolean empty;
    	HashSet<Integer> invalid = new HashSet<>();
    	int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    	public UnionFindSet(char[][] grid) {
    		if (grid.length == 0) {
    			empty = true;
    		} else {
    			empty = false;
    			int rows = grid.length;
    			int cols = grid[0].length;
    			nodes = new int[rows * cols];
    			for (int i = 0; i < rows; ++i) {
    				for (int j = 0; j < cols; ++j) {
    					int index = i * cols + j;
    					if (grid[i][j] == '1') {
    						nodes[index] = index;
    					} else {
    						invalid.add(index);
    					}
    				}
    			}
    			for (int i = 0; i < rows; ++i) {
    				for (int j = 0; j < cols; ++j) {
    					int index = i * cols + j;
    					if (grid[i][j] == '1') {
    						for (int k = 0; k < 4; ++k) {
    							int i0 = i + dir[k][1];
    							int j0 = j + dir[k][0];
    							if (i0 >= 0 && j0 >= 0 && i0 < rows && j0 < cols) {
    								if (grid[i0][j0] == '1') {
    									int index0 = i0 * cols + j0;
    									join(index, index0);
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    
    	public int find(int x) {
    
    		int root = x;
    		while (nodes[root] != root) {
    			root = nodes[root];
    		}
    
    		int path = x, temp;
    		while (nodes[path] != root) {
    			temp = nodes[path];
    			nodes[path] = root;
    			path = temp;
    		}
    
    		return root;
    	}
    
    	public void join(int x, int y) {
    		int rx = find(x), ry = find(y);
    		if (rx != ry) {
    			nodes[rx] = ry;
    		}
    	}
    
    	public int count() {
    		if (empty) {
    			return 0;
    		} else {
    			HashSet<Integer> counter = new HashSet<>();
    			for (int i = 0; i < nodes.length; ++i) {
    				if (!invalid.contains(i)) {
    					counter.add(find(i));
    				}
    			}
    			return counter.size();
    		}
    	}
    }
    
    public class Solution {
        public int numIslands(char[][] grid) {
            return new UnionFindSet(grid).count();
        }
    }
    

Log in to reply
 

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