BiruLyu
6/22/2017 - 4:18 AM

## 305. Number of Islands II.java

``````class UnionFind:
def __init__(self, elems = []):
self.parent = { elem: elem for elem in elems }
self.height = { elem: 1 for elem in elems }

def make_set(self, elem):
self.parent[elem] = elem
self.height[elem] = 1

def find_set(self, elem):
if self.parent[elem] != elem:
self.parent[elem] = self.find_set(self.parent[elem])
return self.parent[elem]

def union(self, elem1, elem2):
root1, root2 = self.find_set(elem1), self.find_set(elem2)
if root1 != root2:

if self.height[root1] > self.height[root2]:
self.parent[root2] = root1
self.height.pop(root2)
else:
if self.height[root1] == self.height[root2]:
self.height[root2] += 1
self.parent[root1] = root2
self.height.pop(root1)``````
``````class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
class Union(object):
def __init__(self):
self.id = {}
self.sz = {}
self.count = 0

self.id[p] = p
self.sz[p] = 1
self.count += 1

def root(self, i):
while i != self.id[i]:
self.id[i] = self.id[self.id[i]]
i = self.id[i]
return i

def unite(self, p, q):
i, j = self.root(p), self.root(q)
if i == j:
return False
if self.sz[i] > self.sz[j]:
i, j = j, i
self.id[i] = j
self.sz[j] += self.sz[i]
self.count -= 1
return True``````
``````public class Solution {

private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind2D islands = new UnionFind2D(m, n);
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
int x = position[0], y = position[1];
for (int[] d : dir) {
int q = islands.getID(x + d[0], y + d[1]);
if (q > 0 && !islands.find(p, q))
islands.unite(p, q);
}
}
return ans;
}
}

class UnionFind2D {
private int[] id;
private int[] sz;
private int m, n, count;

public UnionFind2D(int m, int n) {
this.count = 0;
this.n = n;
this.m = m;
this.id = new int[m * n + 1];
this.sz = new int[m * n + 1];
}

public int index(int x, int y) { return x * n + y + 1; }

public int size() { return this.count; }

public int getID(int x, int y) {
if (0 <= x && x < m && 0<= y && y < n)
return id[index(x, y)];
return 0;
}

public int add(int x, int y) {
int i = index(x, y);
id[i] = i; sz[i] = 1;
++count;
return i;
}

public boolean find(int p, int q) {
return root(p) == root(q);
}

public void unite(int p, int q) {
int i = root(p), j = root(q);
if (sz[i] < sz[j]) { //weighted quick union
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
--count;
}

private int root(int i) {
for (;i != id[i]; i = id[i])
id[i] = id[id[i]]; //path compression
return i;
}
}
//Runtime: 20 ms``````