Java Union And Find Method


  • 0
    D

    I implemented Union and Find Method to solve this problem.

    class UF {
    	private int[] list;
    
    	public UF(int n) {
    		list = new int[n];
    		for (int i = 0; i < n; i++) {
    			list[i] = i;
    		}
    	}
    
    	private int root(int i) {
    		while (i != list[i]) {
    			list[i] = list[list[i]];
    			i = list[i];
    		}
    		return i;
    	}
    
    	public boolean connected(int i, int j) {
    		return root(i) == root(j);
    	}
    
    	public void union(int p, int q) {
    		int i = root(p);
    		int j = root(q);
    		list[i] = j;
    	}
    
    	public int maxUnion(char[][] grid) {
    		Set<Integer> set = new HashSet<>();
    		for (int i = 0; i < list.length; i++) {
    			int x = i / grid[0].length;
    			int y = i % grid[0].length;
    			if (grid[x][y] == '1') {
    				set.add(root(i));
    			}
    		}
    		return set.size();
    	}
    }
    
    public class Solution {
        public int numIslands(char[][] grid) {
                    if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    	
    		int height = grid.length;
    		int width = grid[0].length;
    		int totalSize = height * width;
    		UF uf = new UF(totalSize);
    		for (int i = 0; i < totalSize; i++) {
    			int x = i / width;
    			int y = i % width;
    			int up = x - 1;
    			int right = y + 1;
    			if (up >= 0 && grid[x][y] == grid[up][y] && grid[x][y] == '1')
    				uf.union(i, i - width);
    			if (right < width && grid[x][y] == grid[x][right]
    					&& grid[x][y] == '1')
    				uf.union(i, i + 1);
    		}
    		return uf.maxUnion(grid);
        }
    }
    

Log in to reply
 

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