BiruLyu
5/30/2017 - 6:31 PM

## 200. Number of Islands(Union Find).java

``````public class Solution {
public int numIslands(char[][] grid) {
int count = 0;
int n = grid.length;
if(n == 0) return count;
int m = grid[0].length;

for(int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(grid[i][j] == '1') {
DFS(grid, i, j);
count++;
}
}
}
return count;

}

private void DFS(char[][] grid, int i, int j) {
int m = grid[0].length;
int n = grid.length;
if(i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
grid[i][j] = '0'; // indicated i,j has been visited
DFS(grid, i - 1, j);
DFS(grid, i + 1, j);
DFS(grid, i, j - 1);
DFS(grid, i, j + 1);
}
}

/*
["11110","11010","11000","00000"]
[]
["11000","11000","00100","00011"]
*/``````
``````class UF {

public int count = 0;
public int[] id = null;

public UF(int m, int n, char[][] grid) {
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1') count++;
}
}
id = new int[m * n];
for(int i = 0; i < m * n; i++) {
id[i] = i;
}
}

public int find(int p) {
while(p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}

public boolean isConnected(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot != qRoot) return false;
else return true;
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}

public int numIslands(char[][] grid) {
if(grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
UF uf = new UF(m , n, grid);

for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '0') continue;
int p = i * n + j;
int q;
if(i > 0 && grid[i - 1][j] == '1') {
q = p - n;
uf.union(p, q);
}
if(i < m - 1 && grid[i + 1][j] == '1') {
q = p + n;
uf.union(p, q);
}
if(j > 0 && grid[i][j - 1] == '1') {
q = p - 1;
uf.union(p, q);
}
if(j < n - 1 && grid[i][j + 1] == '1') {
q = p + 1;
uf.union(p, q);
}
}
}
return uf.count;
}``````