以树的形式处理集合的合并及查询
合并：把两个不相交的集合合并为一个集合。
查找：查询两个元素是否在同一个集合里。
思想通过标记该节点所在的组来维护一个森林。
初始化每个节点指向自己本身。
查找用递归的方法查询集合的根节点。
合并先查找两个节点的根节点，然后让其中一个根节点成为另一个根节点的子节点
模板 1.储存定义一个数组 fa表示父节点，并令根的父节点为它本身
int fa[];2.初始化
把所有点全设为一棵树
void init(int n){
for(int i=1;i<=n;i++)
fa[i] = i;
}
3.查询
int Get(int x){
if(x == fa[x])//如果它是根节点
return x;
return Get(fa[x]);//否则递归访问至根节点
}
路径压缩
把每个元素的父节点改为这个集合的根节点。
int Get(int x){
if(x == fa[x]) return x;
return fa[x] = Get(fa[x]);//路径压缩
}
4.合并
合并x与y所在集合，就相当于让x的树根作为y树根的子节点
void Merge(int x,int y){
fa[Get(x)] = Get(y);
}
