并查集真的是太棒了

这个月的leetcode简直就是查并集月啊，打卡没错一题，查并集？查并集？又是查并集！不会！不会！又不会！看题解！好耶我又会了？做题，我是废物。

之前在油管上看Robert Sedgewick巨，佬的视频，我觉得我行了（，但好像重来没有系统的整理过查并集和相关的知识。

在开始之前需要先了解一个概念

1. 动态连通性

并查集：并：合并，查：查找，集：集合。如果有下面的这样一个问题，问题的输入是一列整数对，其中每个类型都表示某种类型的对象，假如阿有一对整数p,q，就可以理解为p，q是相连的，我们假设相连是一种等价关系，就意味这有以下关系

  • 自反性：p和p是相连的
  • 对称性：如果p和q是相连的那么q和p也是相连的
  • 传递性：如果p和q是相连的而且q和r是相连的那么p和也是相连的

等价关系能够把对象分为多个等价类，且两个对象相连时他们才属于同一个等价关系

目标：所以我们应该过滤掉没有意义的帧数对，也就是说如果所有的整数对都不能证明p和q是相连的，那么我们就把它输出，相反如果证明了是相连的那我们应该把他们忽略掉并继续处理下面的整数对。为了达到以上的效果我们需要用一个数据结构来保存这些整数对的信息，并来判断他们某一对象是否相连，于是我们把这个问题的通俗的叫做动态连通性问题

比如我们所熟知的网络，每时每刻就可能要处理数百万对象和数十亿次连接，所以我们需要一个算法帮我们快速的处理类似的问题。所以当我们处理两个可以连接的分量，那我们就可以把他加入到一个集合当中；

2.来设计算法思想

1
2
3
4
5
>void UF(N)//初始化函数
>void unino(p,q)//添加连接
>int find(q)//查找所在的分量标识符
>bool connected(p,q)//判断是否存在于一个分量中
>int count()//计算连通分量的个数

于是我们就需要定义一种数据结果实现以上的思想因此我们需要

  • 定义一种数据结构表示已知连接

  • 实现以上方法

数据结构的性质将直接影响到算法的效率，我们可以用

  • 触点为索引id[]做基本的数据结构来表示所有的分量
  • 使用某个触点的名称做为分量的标识符，也因此每个分量都是由他的触点之一表示的
  • 一开始每个触点都为一个独立的分量，所以我们把分量初始化为i
  • 用find方法来判断它属于那个分量当中
  • coonected用来判断find(p)==find(q)，返回布尔值
  • unino用来连接连个这两个分量

3.先写个demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//
// Created by youmingsama on 2021/4/22.
//
#include "bits/stdc++.h"
using namespace std;
int id[10000];
int count1=0;
int N=0;
void UF(int id[],int *count,int N){
    *count=N;
    for (int i = 0; i < N; ++i) {
        id[i]=i;
    }
}
int count(){
    return count1;

}
int find(int p){
    while (p!=id[p]){
        p=id[p];
    }
    return p;
}
bool connected(int p,int q){
    return find(p)==find(q);
}

void union1(int p, int q){
    int pRoot=find(p);
    int qRoot=find(q);
    if (pRoot==qRoot){
        return;
    }
    id[pRoot]=qRoot;
    count1--;
}
int main(){
    int a[8],b[8];
    int ans=6;
    cin>>N;
    UF(id,&count1,N);
    for (int i = 0; i < 8; ++i) {
        cin>>a[i]>>b[i];
        int p=a[i];
        int q=b[i];
        if (connected(p,q)) continue;
        union1(p,q);
        cout<<p<<"-->"<<q<<endl;
    }
    cout<<count1;
    return 0;
}

关于不同的实现方法

对算法的核心处理无异于是对find函数和union，其他的函数都大同小异对算法的效率影响不大，所以这里我们重点来看find方法和union算法的实现

quick-find算法

一种实现方法是保证id[p]==id[q],这则说明当前p和q是连通的是属于同一个分量，也就说连通分量重的所有触点的id[]必须是相同的，这就意味着connected只需要判断id[p]==id[q]就能判断是否属于同一个连通分量。

如果属于同一个连通分量我们就不需要做任何操作，如果不是属于同一个连通分量我们就需要做连接操作啦。union(p,q)把两个分量合二为一就意味着id[]的值必须是相等的，等于两方任何一方的值(id[p] or id(q))。为此我们需要遍历数组把其中一个集合的id[]，变成另外一个集合的id[]值。

嘛简单整理以下就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>find(p){
>return id[p]
>}
>if connected(p,q)
>continue
>union(p,q){
>int pid=find(p);
>int pid=find(q);
>if pid==qid return;
>for i=0,i<id.length;i++{
  if (id[i]==pid){
      id[i]=qid;
  }
  count--;
>}
>}

在qiuck算法中，find操作显然是很快的，因为它只需要访问id一次，但是对于处理较大型的问题，每一次执行unino都要扫描一id数组 如果使用quick-find算法来解决动态连通性问题最后只得到了一个连通分量，那么至少要调用N-1次union，那么数组访问至少要访问(N-4)(N-1),显然平方级别的在我们处理非常大型的项目上是很难接受的，所以我们需要更快的算法。

quick-union算法