Cacher is the code snippet organizer for pro developers

union find

并查集

作用：
一种用来解决集合查询合并的数据结构。
可以判断两个点是否在一个集合。

find: O(1)
union: O(1)

如果级数太多，find的时候有可能会stack overflow，而且时间复杂度是O(n)。java给32M的栈空间。
为了解决这个问题，在find的时候，做一下压缩，把链状的结构优化为放射状。这样就不会stack overflow，而且时间复杂度接近O(1)

public int find(int x) {
	if (father[x] == 0) {
		return x;
	}
	father[x] = find(father[x]); // 这一步改变了新的老大
	return father[x];
}

template:
public class UnionFind {
  private int[] father = null;
  
  // constructor
  public UnionFind(int[][] matrix, int row, int col) {
    father = new int[row * col];
    for (int i = 0; i < row * col; i++) {
      father[i] = i;
    }
  }
  
  private int find(int x) {
    if (father[x] == 0) {
      return x;
    }
    return father[x] = find(father[x])
  }
  
  public void union(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    if (root_a != root_b) {
      father[root_a] = root_b;
    }
  }
  
  public boolean connected(int a, intb) {
    return find(a) == find(b);
  }
}