Union Find应用
Longest Consecutive Sequence， 用UnionFind维护一个maxSize的变量，代表size最大的那个component的size。用UnionFind可以做到one pass。
public class Solution {
public int longestConsecutive(int[] nums) {
UnionFind uf = new UnionFind();
for (int n: nums) {
if (!uf.parent.containsKey(n)) {
uf.add(n);
}
if (uf.parent.containsKey(n - 1)) {
uf.union(n, n - 1);
}
if (uf.parent.containsKey(n + 1)) {
uf.union(n, n + 1);
}
}
return uf.maxSize;
}
}
class UnionFind {
Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
Map<Integer, Integer> size = new HashMap<Integer, Integer>();
int maxSize = 0;
public void add(int x) {
parent.put(x, x);
size.put(x, 1);
maxSize = Math.max(maxSize, 1);
}
public int find(int x) {
int father = parent.get(x);
while (father != parent.get(father)) {
father = parent.get(father);
}
while (parent.get(x) != father) {
int next = parent.get(x);
parent.put(x, father);
x = next;
}
return father;
}
public void union(int x, int y) {
int x_father = find(x);
int y_father = find(y);
if (x_father != y_father) {
int x_size = size.get(x_father);
int y_size = size.get(y_father);
if (x_size > y_size) {
parent.put(y_father, x_father);
size.put(x_father, x_size + y_size);
maxSize = Math.max(maxSize, size.get(x_father));
} else {
parent.put(x_father, y_father);
size.put(y_father, x_size + y_size);
maxSize = Math.max(maxSize, size.get(y_father));
}
}
}
}
Surrounded regions, 这题用Union Find做的思路就是假设外层有一个点，把所有的在边上的值为'O'的点都跟外层这个点连上，同时把grid内的所有为'O'并且相临的点都连上。最后再扫一遍grid, 如果check都一个点他的值为’O‘且不跟外层我们create出来的那个点连接的话，就把这个点设成'X'。
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
int m = board.length, n = board[0].length;
UnionFind uf = new UnionFind();
uf.add(m * n);
int parent = m * n;
final int[] dx = {0, 0, -1, 1};
final int[] dy = {-1, 1, 0, 0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] != 'O') {
continue;
}
int now = i * n + j;
uf.add(now);
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
uf.union(parent, now);
}
if (i - 1 >= 0 && board[i - 1][j] == 'O') {
int neighbor = (i - 1) * n + j;
uf.union(now, neighbor);
}
if (j - 1 >= 0 && board[i][j - 1] == 'O') {
int neighbor = i * n + j - 1;
uf.union(now, neighbor);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] != 'O') {
continue;
}
int index = i * n + j;
if (!uf.connected(index, parent)) {
board[i][j] = 'X';
}
}
}
}
}
class UnionFind {
Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
Map<Integer, Integer> size = new HashMap<Integer, Integer>();
public void add(int index) {
parent.put(index, index);
size.put(index, 1);
}
public int find(int index) {
int father = parent.get(index);
while (father != parent.get(father)) {
father = parent.get(father);
}
while (parent.get(index) != father) {
int next = parent.get(index);
parent.put(index, father);
index = next;
}
return father;
}
public void union(int x, int y) {
int x_father = find(x);
int y_father = find(y);
if (x_father != y_father) {
int x_size = size.get(x_father);
int y_size = size.get(y_father);
if (x_size > y_size) {
parent.put(y_father, x_father);
size.put(x_father, x_size + y_size);
} else {
parent.put(x_father, y_father);
size.put(y_father, x_size + y_size);
}
}
}
public boolean connected(int x, int y) {
int x_father = find(x);
int y_father = find(y);
return x_father == y_father;
}
}
Graph Valid Tree，用Union Find做的做法就是每次新遇到一个点u和点v，check这两个点是不是connected的，如果是的话，说明图内有环，所以return false。否则的话就把这两个连上，最后check一下，图内是不是只存在一个component。
public class Solution {
public boolean validTree(int n, int[][] edges) {
if (n <= 1) {
return true;
} else if (n != edges.length + 1) {
return false;
}
UnionFind uf = new UnionFind(n);
for (int[] e: edges) {
int u = e[0];
int v = e[1];
if (uf.connected(u, v)) {
return false;
} else {
uf.union(u, v);
}
}
return uf.getNumOfComponent() == 1;
}
}
class UnionFind {
Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
Map<Integer, Integer> size = new HashMap<Integer, Integer>();
private int numOfComponent;
public UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent.put(i, i);
size.put(i, 1);
}
numOfComponent = n;
}
public int find(int x) {
int father = parent.get(x);
while (father != parent.get(father)) {
father = parent.get(father);
}
while (parent.get(x) != father) {
int next = parent.get(x);
parent.put(x, father);
x = next;
}
return father;
}
public void union(int x, int y) {
int x_father = find(x);
int y_father = find(y);
if (x_father != y_father) {
int x_size = size.get(x_father);
int y_size = size.get(y_father);
if (x_size > y_size) {
parent.put(y_father, x_father);
size.put(x_father, x_size + y_size);
} else {
parent.put(x_father, y_father);
size.put(y_father, x_size + y_size);
}
numOfComponent--;
}
}
public boolean connected(int x, int y) {
int x_father = find(x);
int y_father = find(y);
return x_father == y_father;
}
public int getNumOfComponent() {
return numOfComponent;
}
}