数据结构与算法学习笔记----并查集

数据结构与算法学习笔记----并查集

@@ author: 明月清了个风

@@ last edited: 2024.11.27

ps：从这里开始加入原题链接了。

Acwing 836. 合并集合

[原题链接](836. 合并集合 - AcWing题库)

一共有$n$个数，编号是$1\sim n$，最开始每个数各自在一个集合中。

现在要进行$m$个操作，操作共有两种：

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

输入格式

第一行输入整数$N$和$M$

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

输出格式

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

每个结果占一行。

数据范围

$1\le n,m\le 10^5$,

思路

首先思考暴力做法，假设维护两个集合，对于每个集合中的数维护他所属的集合标签，当合并时，需要对集合中的每个数的标签都进行更改，这里时间复杂度是O(N)；对于查询操作而言，直接对比两个数的标签即可，时间复杂度是O(1).

使用并查集可以将合并和查询操作的时间复杂度都保持在近似==O(1)==的程度。

并查集是一种用于处理集合合并和查询操作的数据结构，通常用于处理一些动态连通性问题、图的最小生成树。

通常使用一个数组表示每个元素的父节点，每个集合都可视为一个树形结构：

• parent[i]表示元素i的父节点。
• 初始时，每个元素的父节点指向自己，即parent[i] = i.

对于其基本操作查询和合并而言：

• 查找：通过递归和迭代的方式不断访问父节点，直到找到根节点，也就是parent指向自己的元素。为了优化查询效率，通常使用路径压缩的优化方法，即在查找过程中，将所有访问过的节点直接连接到根节点，从而减少后续查找的路径长度。
• 合并：通常有两种方法，第一种将一个集合直接连接到另一个集合的父节点上；第二种将两个集合都连接到一个新父节点上。这里合并时，可以选择将较矮的那棵树链接到较高的树上， 这样可以避免树的高度过高，这是按秩合并的优化方法

代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) p[i] = i;
    
    while(m --)
    {
        char op[2];
        int a, b;
        cin >> op >> a >> b;
        
        if(op[0] == 'M') p[find(a)] = find(b);
        else
        {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

Acwing 837. 连通块中点的数量

[原题链接](837. 连通块中点的数量 - AcWing题库)

给定一个包含$n$个点（编号为$1\sim n$）的无向图，初始时图中没有边。

现在要进行$m$个操作，操作共有三种：

1. C a b，在点$a$和点$b$之间连一条边，$a$和$b$可能相等。
2. Q1 a b，询问点$a$和点$b$是否在同一个连通块中，$a$和$b$可能相等。
3. Q2 a，询问点$a$所在连通块中点的数量。

输入格式

第一行输入整数$n$和$m$

接下来$m$行，每行包含一个操作指令

输出格式

对于每个询问指令Q1 a b，如果$a$和$b$在同一连通块中，则输出Yes,否则输出No。

于每个询问指令Q2 a，输出一个整数表示点$a$所在连通块中点的数量。

每个结果占一行。

数据范围

$1\le n,m\le 10^5$,

思路

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int cnt[N], p[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) p[i] = i, cnt[i] = 1;
    
    while(m --)
    {
        string op;
        int a, b;
        cin >> op;
        if(op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if(a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if(op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else 
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    
    return 0;
}

Acwing 240. 食物链

[原题链接](240. 食物链 - AcWing题库)

动物王国中有三类动物$A,B,C$，这三类动物的食物链构成了有趣的环形

$A$吃$B$，$B$吃$C$，$C$吃$A$。

现有$N$个动物，以$1\sim N$编号。

每个动物都是$A,B,C$中的一种，但是我们并不直到它到底是哪一种。

有人用两种说法对这$N$个动物所构成的食物链关系进行描述：

第一种说法是1 X Y，表示$X$和$Y$是同类。

第二种说法是2 X Y，表示$X$吃$Y$。

此人对$N$个动物，用上述两种说法，一句接一句地说出$K$句话。这$K$句话有的是真的，有的是假的。

但一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中$X$或$Y$比$N$大，就是假话。
3. 当前的画表示$X$吃$X$，就是假话。

你的任务是根据给定的$N$和$K$句话，输出假话的总数。

输入格式

第一行是两个整数$N$和$K$ ，以一个空格分隔。

以下$K$行每行市三个正整数$D,X,Y$，两数之间用一个空格隔开，其中$D$表示说法的种类。

若$D=1$，则表示$X$和$Y$是同类。

若$D=2$，则表示是$X$ 吃$Y$。

输出格式

只有一个整数，表示假话的数目。

数据范围

$1\le N\le 50000$,

$0\le K\le 100000$

思路

这里用的是y总讲的带权并查集。

并查集的基本操作是查询和合并，但是在这个过程中可以维护很多信息，比如上一题中集合中点的个数，这一题中，我们同样可以维护集合中点之间的关系，因为对一个集合而言，父节点是相同的，因此可以根据点与父节点的关系，确定点与点的关系。

首先解释题意

• 第一个假话条件：当前的话与前面的某些真的话冲突，就是假话。

  例如，已经说过$A$吃$B$了，后面又说了$B$吃$A$，这就是假话。

• 第二个假话条件：当前的话中$X$或$Y$比$N$大，就是假话

  例如，给出的$N$为100，但是说有$101$号动物，就是假话

• 第三个假话条件：当前的话表示$X$吃$X$，就是假话

  这很好理解。

还要注意的是，当前的话如果判断为真，那么就要对并查集进行维护了。

到这我们已经可以有了基本的代码框架

int res = 0;
while(m --)  // 挨个读入所有的话
{
    int t, x, y;
    cin >> t >> x >> y;
   	if(x > n || y > n) res ++;   // 最简单的第二个条件
    else
    {
	// 另外两种假话条件的判断逻辑
    }
}

边权的维护

首先不管是第一种还是第二种说法，只有x和y已经在同一个集合中，也就是之前已经给他们指定过关系之后才会出现假话，所以首先要找到他们的父节点int px = find(x), py = find(y)并进行判断if(px == py)

针对两种说法中x和y的关系，使用边权解决，通过维护数组d[N]确定。

上面已经说过同一个集合中的点都根节点有关，因此通过其与根节点的关系，可以确定他们之间的关系，规则定义如下：

• 点到根节点的距离mod 3 = 1:表示可以吃根节点。

• 点到根节点的距离mod 3 = 2:表示可以被根节点吃。

• 点到根节点的距离mod 3 = 0:表示和根节点是同类。

首先看x的边权d[x]的含义：x到其父节点的距离，对于每一个点，初始值都为0。这里有个注意点：父节点和根节点的关系。

对于每一个点而言其初始父节点就是自己，根节点也是自己，d[x]初始值自然为1。

但是并查集是通过树形结构存储的，经过一系列合并操作后，父节点和所在集合的根节点就不是一个了，在路径压缩操作之前，每个点都有两个距离，一个是到父节点的距离，一个是到根节点的距离，但是经过路径压缩之后，一个点到根节点路径上所有点的父节点都会变成根节点，因此，经过路径压缩之后的d[x]才是到集合根节点的距离，这也是为什么在这题的路径压缩中，需要额外维护d[x]信息的原因，维护代码如下：

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    
    return p[x];
}

对于一个点而言，当其要进行路径压缩时，他到根节点的距离是到父节点的距离+父节点到根节点的距离,因此首先递归更新父节点及父节点之上所有的点的距离int t = find(p[x])，然后用这个距离更新当前点到根节点的距离d[x] += d[p[x]],最后对这个点进行路径压缩将其指向根节点（此时也是父节点）p[x] = t。

另外两个假话的判断逻辑

由于我们在寻找父节点的时候已经进行了每个点到根节点距离的更新（也就是点与根节点的关系）。

因此，对于第一种说法1 X Y，当(d[x] - d[y]) % 3 == 0时成立，若不为0则为假话

对于第二种说法2 X Y,当(d[x] - d[y] - 1) % 3 == 0时成立，若不为0则为假话，这里解释一下，因为说法二表示$X$吃$Y$，因此，$X$应被根节点吃d[x] mod 3 == 2，而$Y$吃根节点d[y] mod 3 == 1,这样构成的环形才是$X$吃$Y$。

代码

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    
    return p[x];
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) p[i] = i;
    
    int res = 0;
    while(m --)
    {
        int t, x, y;
        cin >> t >> x >> y;
        
        if(x > n || y > n) res ++;
        else
        {
            int px = find(x), py = find(y);
            if(t == 1)
            {
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else if(px != py)
                {
                    p[px] = p[y];
                    d[px] = d[y] - d[x];
                    
                }
            }
            else 
            {
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else if(px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    
    printf("%d\n", res);

    return 0;
}