2021年hznu寒假集训第二天
关键词：代表元
解决问题：问题的朴素解法
概念：并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性，如下图所示，这是一个并查集，其中箭头表示父子关系。
优化
路径压缩
我们通常把路径优化后的结果叫做菊花图.
即将上面的图变成下面的
接下来我们来介绍一下路径压缩.
C的父节点是B，而B的父节点是A，所以我们就可以把A设为C的父节点。
接下来看一下代码：
int find(int x)
{
return x==parent[x]?parent[x]:parent[x]=find(parent[x]);
}
合并
比如这题，我们想要证明环存在，进行完路径压缩，我们要合并。
合并就是将两个集变成一个集
如图所示，0、2的父节点是1, 3的父节点是4，要想这两个集有关联，我们要尝试将他们的父节点相关联，例如这样
那这个过程我们就把他叫做合并。
下面是它的代码：
void Union(int x,int y){
int fx=find(x),fy=find(y);
//找出父节点
if(fx!=fy)
//证明父节点不相同，即他们是在两个集合里面
parent(fx)=fy;
//则将其中一个父节点y设为另一个父节点x的父节点
}
下面我们来解决一下上面证明环存在的问题
#include<stdio.h>
#include<stdlib.h>
#define VERTICES 6
void initialise(int parent[]){
int i;
for(i=0;i<VERTICES;i++){
parent[i]=-1;
}
}
int find_root(int x,int parent[]){
int x_root=x;
while(parent[x_root]!=-1){
x_root=parent[x_root];
}
return x_root;
}
/*1- union successfully,0-failed*/
int union_vertices(int x,int y,int parent[]){
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root){
return 0;
}
else{
parent[x_root]=y_root;
return 1;
}
}
int main(){
int parent[VERTICES]={0};
int edges[6][2]={
{0,1},{1,2},{1,3},
{2,4},{3,4},{2,5}
};
initialise(parent);
int i;
for(i=0;i<6;i++){
int x=edge[i][0];
int y=edge[i][1];
if(union_vertices(x,y,parent)==0){
printf("Cycle detected!\n");
exit(0);
}
}
printf("NO cycles found.\n");
return 0;
}
但是这串代码有一个缺陷，如果我们的图是
比如第一次union（0,1），第二次（1,2），第三次（2,3）……
这个时候，会形成一个特别长的链，在查找parent的时候就会执行特别多次，时间复杂度是log n级别的
所以我们这个时候要再进行优化。
按秩合并
首先我们要引入秩的概念。
rank：指代树的高度
这棵树x的高度是3；
而这棵树y的高度则是1；
如果我们把树y接在树x上，即x作为y的parent，那么，他的rank并不发生改变；
反过来，他的rank变成了4；
后者显然是我们不希望的，所以我们要按秩合并。
if rank[x]>rank[y]
parent[y]=x;
//rank 不变->x
else
parent[x]=y;
之前那道题的代码就可以优化了
#include<stdio.h>
#include<stdlib.h>
#define VERTICES 6
void initialise(int parent[],int rank[]){
int i;
for(i=0;i<VERTICES;i++){
parent[i]=-1;
rank[i]=0;
}
}
int find_root(int x,int parent[]){
int x_root=x;
while(parent[x_root]!=-1){
x_root=parent[x_root];
}
return x_root;
}
/*1- union successfully,0-failed*/
int union_vertices(int x,int y,int parent[],int rank[]){
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root){
return 0;
}
else{
//parent[x_root]=y_root;
if(rank[x_root]>rank[y_root]){
parent[y_root]=x_root;
}
else{
parent[x_root]=y_root;
}
return 1;
}
}
int main(){
int parent[VERTICES]={0};
int rank[VERTICES]={0};
int edges[6][2]={
{0,1},{1,2},{1,3},
{2,4},{3,4},{2,5}
};
initialise(parent,rank);
int i;
for(i=0;i<6;i++){
int x=edge[i][0];
int y=edge[i][1];
if(union_vertices(x,y,parent,rank)==0){
printf("Cycle detected!\n");
exit(0);
}
}
printf("NO cycles found.\n");
return 0;
}