并查集 将集合在逻辑上表示为树结构。
void Initial() {
for(int i=0; i<n; i++) {
father[i]=i;
height[i]=0;
}
return ;
}
int Find(int x) { //路径压缩
if(x!=father[x]) {
father[x]=Find(father[x]);
}
return father[x];
}
void Union(int x,int y) { //合并集合
x=Find(x);
y=Find(y);
if(x!=y) {
if(height[x]>height[y]) {
father[y]=x;
} else if(height[x]<height[y]) {
father[x]=y;
} else {
father[y]=x;
height[x]++;
}
}
return ; //防止成环
for(int i=0; i<n; i++) {
father[i]=i;
height[i]=0;
}
return ;
}
int Find(int x) { //路径压缩
if(x!=father[x]) {
father[x]=Find(father[x]);
}
return father[x];
}
void Union(int x,int y) { //合并集合
x=Find(x);
y=Find(y);
if(x!=y) {
if(height[x]>height[y]) {
father[y]=x;
} else if(height[x]<height[y]) {
father[x]=y;
} else {
father[y]=x;
height[x]++;
}
}
return ; //防止成环
}
只能判断是否为连通图，或用来求图的连通分量的个数。
不能认为只有一个连通分量其一定就为树。
树是有向的。 连通分量无向！！
其可能有多个根结点。
