Clear & Easy Java Union-Find Solution


  • 0
    F

    public class Solution {
    int[] nodes;
    int n, m;

    public int numIslands(char[][] grid) {
    	if (grid == null || grid.length == 0)
    		return 0;
    	n = grid.length;
    	m = grid[0].length;
    	nodes = new int[n * m];
    	Arrays.fill(nodes, -1);
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			int cur = i * m + j;
    			if (grid[i][j] == '1' && nodes[cur] == -1) {
    				nodes[cur] = cur;
    				cur = Union(grid, i - 1, j, cur);
    				cur = Union(grid, i + 1, j, cur);
    				cur = Union(grid, i, j - 1, cur);
    				cur = Union(grid, i, j + 1, cur);
    			}
    		}
    	}
    	int res = 0;
    	for (int i = 0; i < m * n; i++) {
    		if (i == nodes[i]) {
    			res++;				
    		}
    	}
    
    	return res;
    }
    
    private int Union(char[][] grid, int i, int j, int cur) {
    	int newCur = i * m + j;
    	if (i < 0 || i > n - 1 || j < 0 || j > m - 1 || nodes[newCur] == -1)
    		return cur;
    
    	newCur = find(newCur);
    	if (newCur != cur) {
    		nodes[cur] = newCur;
    	}
    	return newCur;
    
    }
    
    private int find(int cur) {
    	while (cur != nodes[cur]) {
    		nodes[cur] = nodes[nodes[cur]];
    		cur = nodes[cur];
    	}
    	return cur;
    
    }
    

    }


Log in to reply
 

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