CS61B 笔记系列 14 Disjoint Sets


14.1 Dynamic Connectivity and the Disjoint Sets Problem

本节讲的是 “union-find” 算法,中文翻译就很熟悉了:并查集

14.1.1 The Disjoint Sets Data Structure

上来那开宗明义,啥是并查集啊!

The Disjoint Sets data structure has two operations:

  • connect(x, y): Connects x and y.
  • isConnected(x, y): Returns true if x and y are connected. Connections can be transitive, i.e. they don’t need to be direct.

并查集只有两个操作:

  • 合并/连接
  • 查询
public interface DisjointSets {
    void connect(int p, int q);
    boolean isConnected(int p, int q);
}

14.1.2 The Naive Approach

这个其实没意思,就是这个 API 它用了会是啥效果

https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502085444.png

14.2 Quick Find

如何实现呢:

若尝试 Map , Slow because you have to iterate to find which set something belongs to.

这里其实的意思是,我们选择的底层的实现方式是会影响效率的,国内的挨过数据结构毒打的同学就悟了:这就是所谓的逻辑结构和物理结构嘛,不同物理结构是实现会导致不同的操作呗

14.2.1 SETS

Idea #1: List of sets of integers, e.g. [{0, 1, 2, 4}, {3, 5}, {6}] : List>.

初始化 : [{0}, {1}, {2}, {3}, {4}, {5}, {6}]

若是要查找 :Requires iterating through all the sets to find anything. Θ(N).

https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502090151.png

Important point: By deciding to use a List of Sets, we have doomed ourselves to complexity and bad performance.

用错了实现数据结构,导致了这样的情况

14.2.1 LIST

Idea #2: list of integers where ith entry gives set number (a.k.a. “id”) of item i.

这个的意思是:将 int[x] 指向其根节点

https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502090603.png
https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502090703.png
package lec14_Disjiont_Sets;

public class QuickFindDS implements DisjointSets {
    private int[] id;

    @Override
    public boolean isConnected(int p, int q) {
        return id[p] == id[q];
    }

    @Override
    public void connect(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }
        }
    }

    // 初始化,所有的元素都是独立的
    public QuickFindDS(int N) {
        id = new int[N];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }
}

这里需要强调的是:

虽然 isConnected 是极快的,但是 connect 是很慢的,为什么,那每次遍历都往祖坟上刨肯定慢啊

https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502090647.png

14.3 Quick Union

为了解决 connect 的速度问题,我们要进行一个改进

跳过那些巴拉巴拉的东西,让 int[x]指向其父节点而不是root,而root节点值为 -1

package lec14_Disjiont_Sets;

public class QuickUnionDS implements DisjointSets {
    private int[] parent;
    public QuickUnionDS(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    private int find(int p ){
        int r = p;
        while (parent[r] >=0 )
            { r = parent[r]; }
        return r;
    }

    @Override
    public void connect(int p, int q) {
        int i = find(p);
        int j = find(q);
        parent[i] = j;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}
https://raw.githubusercontent.com/biepin7/CloudForImg/master/20220502094900.png

14.4 Weighted Quick Union

略,其实是油管的翻译有问题了,而且这玩意我考研不考

14.5 Path Compression (CS170 Preview)

ACWING

并查集:

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

暴力存储:

尝试数组存储 :belong[x] = a (x的集合)

if(belong[x] == belong[y]) O(1)

但是合并那是及其耗时的,怎么办呢:

基本原理:

用树的形式维护所有集合,每一个集合用一棵树维护,其编号为根节点的编号,对每一个点都存储其父节点p[x]

  1. 如何判断树根: if[p[x] == x]
  2. 如何求 x 的集合编号 :while(p[x]≠x) x = p[x]; //这里会导致高时间复杂度
  3. 如何合并两个集合:一个根做另一个根的子节点 p[x] = y

对 2. 的优化,每次找到之后,将路径上的所有点都指向根节点(所谓的路径压缩)

还有一个优化:按秩合并?还有 路径减半 路径分裂吗,但是关我屁事,会用路径压缩写就完事了

836. 合并集合

一共有 nn 个数,编号是 1∼n1∼n,最开始每个数各自在一个集合中。

现在要进行 mm 个操作,操作共有两种:

  1. M a b,将编号为  和  的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作; a a b b
  2. Q a b,询问编号为  和  的两个数是否在同一个集合中; a a b b

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b,都要输出一个结果,如果 aa 和 bb 在同一集合内,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:

Yes
No
Yes
#include "iostream"
using namespace std;

const int N = 100010;

int p[N]; 

int n,m;

int find(int x) // return x的root + 路径压缩
{
    if(p[x]!= x) p[x] = find(p[x]);
    return p[x];

    // return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    cin>>n>>m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- ){
        // char op[2];
        char c;
        int a,b;
        // cin >>op>>a>>b;
        cin >>c>>a>>b;

        // if(op[0] == 'M') p[find(a)] = find(b);
        if(c == 'M') p[find(a)] = find(b);
        else {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }

    }
    return 0;
}

发表评论