并查集

并查集是一个树形的数据结构，能够实现快速查询两个数是否属于同一个集合。

并查集虽说是树形的结构，但是一个节点只记录了父亲，不记录子节点，因为记录子节点完全没有必要。

怎么标记两个节点属于一个集合？比如两个节点是a和b，则只需要fa(a) = fa(b),fa(a)是a最原始的祖先。这样的话两棵树就连在了一起。要查询两个节点是否在同一个集合，只需要分别计算fa(a)和fa(b)，只要两者一样就代表他们在同一颗树，也就是属于同一个集合。

当然，并查集只能只有上述两个操作，不能够修改节点集合之间的关系，也不能嵌套之类的。如果真的要实现这些复杂的操作，那么只能够求靠动态树了。

并查集一个操作的复杂度在于找父亲，可以每次merge的时候让这棵树平衡一点加快并查集的查询速度。

并查集的一个应用就是求最小生成树的kruskal算法。每次选择最短的边，把两个相连的点标记为在同一个集合，知道所有点都加入集合，就得到最小生成树了。

下面是并查集一个实现：

/***********************************************\
 |Author: YMC
 |Created Time: 2015/3/26 22:17:52
 |File Name: a.cpp
 |Description: 
\***********************************************/

int n,m;
int father[5000];
void init(int n) {
    srep(i,n) father[i] = i;
}

int find(int v) {
    return father[v] = father[v] == v ? v : find(father[v]);    //可降低并查集高度
}

bool merge(int a,int b) {
    int x = find(a);
    int y = find(b);
    if(x == y) return false;
    father[x] = y;
    return true;
}