当前位置 : 主页 > 编程语言 > 其它开发 >

关于并查集

来源:互联网 收集:自由互联 发布时间:2022-05-30
并查集,顾名思义,就是合并、查找集合: 对于一个集合S={a1, a2, ..., an-1, an},我们还可以对集合S进一步划分: S1,S2,...,Sm-1,Sm。我们希望能够快速确定S中的两两元素是否属于S的同一子集

并查集,顾名思义,就是合并、查找集合:

对于一个集合S={a1, a2, ..., an-1, an},我们还可以对集合S进一步划分: S1,S2,...,Sm-1,Sm。我们希望能够快速确定S中的两两元素是否属于S的同一子集。

主要是两个操作:

1、Find查找元素所属集合

2、Union合并两个集合成一个新的集合

 

基本解析:

可以用树来表示这种数据结构——集合。最初的时候每一个元素都是一个集合 。                  

那如果我们现在想把{0}和{1}合并成一个集合{0,1}该怎么办呢?那就要自定义并使用Union函数(具体代码实现下文会提及)

然而如果我想判断两个元素是否在同一个集合中,就可以用Find函数来实现

 

代码思想:

首先定义一个parent数组来表示元素的父结点。

对于Find操作,因为每个集合都会有一个打头的根结点,所以对于任意两个元素,我们只要看他们所属的集合(树)的leader(根结点)是否是一样的就可以判断他们是否在同一个集合内

int find(int x)
{
    return parent[x] == x ? x : find(parent[x]);
}

当然,这样写时间会短很多:

 1 int find(int x)
 2 {
 3        int haha=x;
 4     while(parent[x]!=x)
 5     {
 6         x=parent[x];
 7     }
 8     while(parent[haha]!=haha)
 9     {
10         haha=parent[haha];
11         parent[haha]=x;
12     }
13     return x;
14 }

这就是find操作,值得注意的是,如果x=parent[x],那就说明已经找到了根结点。那就可以跳出并返回自己了。(也就是元素的根节点),最后我们只要比较find[x]是否等于find[y]就可以判断x和y是否在同一集合内(是否有同样的根节点)

 

那怎样实现union操作呢?

传入两个元素,分别找到根节点,使根节点p1的父节点为p2,即将p1为根节点的这棵树合并到p2为根节点的树上。

void to_union(int x1, int x2) 
{
    int p1 = find(x1);
    int p2 = find(x2);
    parent[p1] = p2;
}

 

哈哈,都听懂了吧,但别高兴的太早!!!

用脚指头想想,每次find的操作复杂度都是树的高度o(h),如果这棵树的每一个结点(根节点和叶节点除外)都只有一个出度和一个入读,那很好,你就得到了o(n)的复杂度。。。

这可不是AC人士的标配啊,那可咋没办?

 

 方法一:那就要路径压缩啦!!!

“路径压缩”。在执行Find的过程中,将路径上的所有节点都直接连接到根节点上。

 方法二:"按秩合并"

实际上就是在合并两棵树时,将高度较小的树合并到高度较大的树上。这里我们使用“秩”(rank)代替高度,秩表示高度的上界,通常情况我们令只有一个节点的树的秩为0,严格来说,rank + 1才是高度的上界;两棵秩分别为r1、r2的树合并,如果秩不相等,我们将秩小的树合并到秩大的树上,这样就能保证新树秩不大于原来的任意一棵树。如果r1与r2相等,两棵树任意合并,并令新树的秩为r1 + 1
代码:
 1 int find(int x)
 2 {
 3     if(x==parent[x])
 4     {
 5         return x;
 6     }
 7     else 
 8     {
 9         parent[x]=find(parent[x]);
10         return find(parent[x]);
11     }
12 }
13 
14 void to_union(int x1, int x2)
15 {
16     int f1=find(x1);
17     int f2=find(x2);
18     if(rank[f1]>rank[f2])
19     {
20         parent[f2]=f1;
21     }
22     else
23     {
24         parent[f1]=f2;
25         if(rank[f1]==rank[f2])
26         {
27             rank[f2]++;
28         }
29     }
30 }

就先到这吧

拜拜!



网友评论