代码样板（来自jisuanke）
class DisjointSet {
private:
int *father;
public:
DisjointSet(int size) {
father = new int[size];
for (int i = 0; i < size; ++i) {
father[i] = i;
}
}
~DisjointSet() {
delete[] father;
}
int find_set(int node) {
if (father[node] != node) {
return find_set(father[node]);
}
return node;
}
bool merge(int node1,int node2){
int ancestor1=find_set(node1);
int ancestor2=find_set(node2);
if(ancestor1!=ancestor2){
father[ancestor1]=ancestor2;
return true;
}
return false;
}
};
说明
并查集有两个最重要的操作：merge和find
整个class有一个私有数组成员变量father，记录每一个对应节点的父亲——初始化时所有节点的父亲都被设定成自己。
find操作的流程：首先查看待查节点node的father是不是自己，如果是则直接返回node，而如果不是，则返回对node的father递归调用的结果。
merge操作的流程：调用find操作分别找出node1和node2所属的集合根节点，然后判断两个根节点是否相等。如果相等，则返回false（即没有进行merge操作）；如果不相等，则将node1所属根节点的父亲设置成node2所属根节点，然后返回true
