Catshao

用户名：Catshao

访问量：25454

签　名：

stO KHIN Orz

等　　级
排　　名	174
经　　验	6732
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

【饿搞向】打印图案-题解
浏览：4612

舍罕王的失算-O(1)解法（Python & C++）
浏览：1066

数据结构-表达式求值-eval（Python代码）
浏览：399

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

并查集详解（C++代码）（小白向）

　　作者: Catshao　　　　发表时间：2021-02-12 10:29:24 浏览：889　|　评论：1　

原题链接：畅通工程

# Part 1 并查集

并查集是一种集合，它有两种操作：并、查。
1. 并：合拼两个集合。
2. 查：查找节点的根节点。

并查集使用一个数组`parent`实现，记录里每一个定点的父亲。
例如：`parent[3] = 5`，那么5就是3的父节点。

**一棵树**的根节点的双亲是它自己`parent[i] = i`，在初始化的时候，每一个定点都是一棵独立的树，所以对于每一个i，都有`parent[i] = i`。

例子：
![并查集样例](http://cat-shao.gitee.io/mypic/setExample.png)
```cpp
parent[1] = 1;
parent[2] = 1;
parent[3] = 3;
parent[4] = 3;
parnet[5] = 4;
parent[6] = 3;
```

## 操作

### 初始化

前面提到过，每一个节点都是一棵树，就有如下代码：

```cpp
disjointSet() {
    for (int i = 0; i < MAX_N; ++i) {
        parent[i] = i;
    }
}
```

### 合拼

![并查集合拼](http://cat-shao.gitee.io/mypic/setUnite.png)

合拼只需要将一个**根节点**指向**另一个根节点**即可。
还有一种情况如下：

![并查集合拼](http://cat-shao.gitee.io/mypic/setCannotUnite.png)

如图，节点4和3的双亲节点是一样的，不能合拼（合拼合了个寂寞）。

```cpp
bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
        return false;
    }
    parent[rootY] = rootX;
    return true;
}
```

由于树的高度大概为`logn`，所以合拼的时间复杂度为`O(logn)`（合拼为`O(1)`，查找为`O(logn)`）

### 查找

根节点的特征为`parent[i] = i`，所以我们可以一直**向上**查找，直到`parent[i] = i`

```cpp
int find(int x) {
    while (x != parent[x]) { // x不是根节点
        x = parent[x]; // 向上
    }
    return x;
}
```

#### 路径压缩

在很多次合拼之后，整棵树的高度可能会很高，如何将整棵树的高度降下来呢？

![并查集查找](http://cat-shao.gitee.io/mypic/setFind.png)

我们只需要将**沿途**的节点都指向**根节点**，整棵树的高度就会下降，我们称之为**路径压缩**

路径压缩的代码如果用`while`来写需要查找两次，故使用递归来写路径压缩

```cpp
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}
```

## 代码

这个代码不是畅通工程的，是并查集的。畅通工程会在Part 2 讲。

```cpp
class disjointSet {
public:
    int parent[MAX_N];

disjointSet() {
        for (int i = 0; i < MAX_N; ++i) {
            parent[i] = i;
        }
    }

int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        parent[rootY] = rootX;
        return true;
    }

bool same(int x, int y) {
        return find(x) == find(y);
    }
};
```

# Part 2 畅通工程

> 对每个测试用例，在1行里输出最少还需要建设的道路数目。

这句话提醒了我们，图可能是不连通的。

如果图不连通，我们使用并查集来存这个图，就会是一片森林。

![森林](http://cat-shao.gitee.io/mypic/forest.png)

每一棵树都会有它对应的根节点，可以看到上面的图中有三个根节点。使这三棵树联通需要几条路径呢？需要两条。所以`需要的路径 = 根节点个数 - 1`

我们来理一下过程：
1. 循环输入路径，合拼路径左右的树。`unite(路径起点，路径终点)`
2. 遍历整个并查集，查看有多少个根节点，输出`根节点个数 - 1`

## 代码

```cpp
#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1000000000;
const int MAX_N = 1000;

class disjointSet {
public:
    int parent[MAX_N];

disjointSet() {
        for (int i = 0; i < MAX_N; ++i) {
            parent[i] = i;
        }
    }

int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int disjointSetMain()
{
    int x, y, n, m;
    while (~scanf("%d", &n) && n != 0) {
        scanf("%d", &m);
        disjointSet parent = disjointSet();
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            parent.unite(x, y);
        }
        int count = 0;
        for (int i = 1; i <= n; ++i) {
            if (parent.parent[i] == i) {
                count ++;
            }
        }
        printf("%d\n", count - 1);
    }
}

int main()
{
    disjointSetMain();
}
```

--------------

今天大年初一，祝各位新年快乐！

参考：
1. 《算法笔记》
2. [畅通工程-题解(C++代码)并查集](https://blog.dotcpp.com/a/60998)

0.0分

195 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

斯巴达

大佬, 你这个画图用的是啥软件? 看着用来分析算法挺方便

2022-03-12 17:23:45

Catshao

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

化学品问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

并查集详解（C++代码）（小白向）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

矩阵加法（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

1128题解（返回值为数组的情况）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

化学品问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

并查集详解（C++代码）（小白向）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

矩阵加法 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

1128题解（返回值为数组的情况）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

化学品问题（C语言代码）

　　评论区

矩阵加法（C语言代码）