【ALGORITHM.0x00】并查集算法浅析

本文最后更新于：2025年3月8日 早上

集你太美，babe！

注：比古老的 CSDN 博客更古老的新浪博客内容拾遗：）

注2：本文经过翻新已正式上线西安电子科技大学 2020 年下学期选修课《ACM程序设计》的课前演讲！欢迎大家 11 月 2 号晚上前来 B-106 听什么厉害的 OI 奖都没拿过的作者吹水（什么鬼）！

0x00. 绪论

在正式介绍并查集之前，我们先来简单看看这样的一个问题：

Description

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

Input

第一行：三个整数n,m,p，（n< =5000,m< =5000,p< =5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1< =Mi，Mj< =N，表示Mi和Mj具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

Output

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

来源：【洛谷1551《亲戚》】https://www.luogu.org/problem/P1551

简化一下：给定n组亲戚关系，询问i对亲戚ai与bi间是否存在亲戚关系，如何解决这个问题呢？

你可能很快就能给出回答：当然是设定数个集合将 从属不同关系的亲戚 划分到 不同的集合 当中啦！

那么，具体实现呢？

若是每一次读取亲戚关系都要遍历所有集合查找一次 “该亲戚是否属于第一个集合、第二个集合……” ，很显然，反复的查找使得我们的时间复杂度大幅度提高，最高甚至可能会有 O(M^2^Q)

而无论是在ACM，NOI，还是其他的算法竞赛当中，若是在那台小破机子上跑这样的无脑且低效率的算法，无疑是要TLE的……

于是便有了 时间复杂度仅为O(N+M+Q)的 并查集算法的出现

（由于作者水平有限，因而只给出入门级别的并查集介绍与实现思路）

0x01. 简介：什么是并查集？

并查集算法是一种用于快速查询不同元素所属集合的算法，常见于各类oi当中，为了优化查找时间而开发出的一种特殊的算法

某种程度而言，并查集是一种较为特殊的树型的数据结构（森林），其核心思路是 将多个相同属性的节点连接到同一棵树中（路径压缩） ，从而能用于快速处理不相交的集合的合并与查询的问题

时间复杂度为线性的O(N+M+Q)

基本原理：优化路径压缩

在初始时， 每个元素都单独作为一个独立的集合（一棵只有根节点的树） ，并 在查询过程中进行路径压缩 ，将所有有关系的元素同归于一个集合之下：

  • 初始化：将每个节点初始化为一个独立的集合—— 节点指向自身
  • 建立关系：对于存在关系的两个节点，将其归为同一集合—— 被合并节点指向另一节点
  • 查询： 节点的归属集合为其所在树的根节点 ，在查询过程中将路径上经过的节点 都更新为指向根节点 ——完成路径压缩

例题：洛谷 P1551

题目我们已经在前面摘抄了，现在我们来看解法

（1）初始化元素集合

首先建立一个全局数组，并将其中的值全部初始化为自身（即，为每个可能存在的人单独开一个集合）

数组的每一个元素表示一个可能存在的亲戚，其值即为所属的并查集（树）

1
2
3
4
int u[5001];
// ......
for(int i=0;i<5001;i++)
    u[i]=i;

（2）建立关系：集合合并

当我们读入一组亲戚关系之后，我们利用并查集的特性，搜寻这一对元素分别所属的集合，并进行对比，若不一致，则将两集合进行合并：

1
2
3
4
5
6
7
8
9
10
for(i=0;i<m;i++)
{
    cin>>a>>b;
    a=find_x(a);
    b=find_x(b);
    if(a!=b) {
        u[a]=b;

    }
}

（3）搜索函数：找寻元素最终所属的集合

这里运用了简单的递归来实现这一功能：

若是所查找元素与自身的值不相同，说明该元素属于其值所在元素，于是我们再查找其值所在元素，一层一层查找下去便能找到最终其所属的“根集合”

若是所查找元素与自身的值相等，那么他就是这一个并查集的“根元素”，于是我们便将最终归属的“根集合”返回至上层函数

话不多说，上具体代码实现：

1
2
3
4
5
6
int find_x(int x)
{
    if(x==u[x])
        return x;
    return find_x(u[x]);
}

（4）对比元素所属集合是否相同

这里没什么需要解析的，利用上文所给出的搜索函数查找所需比对关系的元素所属的集合，进行对比，即可知道其是否同属于一个集合
代码实现：

1
2
3
4
5
6
7
cin>>a>>b;
a=find_x(a);
b=find_x(b);
if(a==b)
    cout<<"Yes"<<endl;
else
    cout<<"No"<<endl;

（5）完整代码实现

（洛谷1551题解）

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
#include<iostream>
#include<cstdio>
using namespace std;

int find_x(int x);

int u[5001]={0};

int main(void)
{
    int n,m,p,i,a,b;
    for(i=0;i<5001;i++)
        u[i]=i;
    cin>>n>>m>>p;
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        a=find_x(a);
        b=find_x(b);
        if(a!=b)
            u[a]=b;
    }
    for(i=0;i<p;i++)
    {
        cin>>a>>b;
        a=find_x(a);
        b=find_x(b);
        if(a==b)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

int find_x(int x)
{
    if(x==u[x])
        return x;
    return find_x(u[x]);
}

0x02. 进阶：二维空间上的并查集应用

除了可以应用于“亲戚关系”这样的图结构当中，并查集还能用于图上的结构相交的应用，下面我们来看一道 OI 实战中出现过的题目（虽然说作者当年没能很好地做出来…）

例题：NOIP 2017 提高组 Day2 T1 - 奶酪（普及/提高-）

题目描述

（实在是没法把原格式很好地复制进来…）

来源：【洛谷P3958 [NOIP 2017 提高组] 奶酪】https://www.luogu.com.cn/problem/P3958

解题思路

咋一看我们需要判断多个洞之间非常复杂的连接问题，但实际上我们只需要判断从下面的洞是否能够走到上面的洞（说了好像没说……）

但既然当两个洞相交时，这两个洞是连通的，我们不难想到的是这同样可以使用并查集的集合约束技术来解决这个问题——也就是说 对于相交的两个洞，我们可以认为他们属于同一个集合

因此，我们最后需要求解的只是 是否存在与上层的洞属于同一集合的下层的洞

（1）初始化元素集合

我们首先要为每个洞独立定义一个集合，并定义顶部洞集合与底部洞集合，在读取过程中同步初始化这三个数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int u[10005];
int top[100005];
int bottom[100005];
long long int x_pos[100005];
long long int y_pos[100005];
long long int z_pos[100005];

int main(void){
    //...
        long long int n, h, r, r_sqrt_4, top_count = 0, bottom_count = 0;
        bool flag =  false;
        long long int x, y, z;
        scanf("%lld%lld%lld",&n,&h,&r);
        for(int i=1;i<=n;i++)u[i] = i;
        for(int i=1;i<=n;i++){            
            scanf("%lld%lld%lld",&x,&y,&z);x_pos[i] = x;y_pos[i] = y;z_pos[i] = z;
            if(z+r >= h)top[top_count++] = i;
            if(z-r <= 0)bottom[bottom_count++] = i;

（2）建立关系：集合合并

每读取一个洞，我们便计算其与已有的洞之间的距离，若是连通，则进行合并：

1
2
3
4
5
6
7
8
9
10
#define distance_sqrt(x1,x2,y1,y2,z1,z2) (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2)

//...

int main(void){
    //...
            for(int j=1;j<i;j++)
                if(distance_sqrt(x_pos[j],x,y_pos[j],y,z_pos[j],z) <= r*r*4)
                    union_set(find_u(i),find_u(j));
        }

（3）搜索函数与合并函数

和前面一样，一边递归一边寻找根节点以同步实现路径压缩，不过似乎也可以递归变递推：

1
2
3
4
5
6
7
8
9
10
int find_u(int n)
{
    return n == u[n] ? n : (u[n] = find_u(u[n]));
}

void union_set(int a, int b)
{
    u[find_u(a)] = find_u(b);
}

（4）对比元素所属集合是否相同

这里就是对比顶部洞所属集合与底部洞所属集合了，找到这样的连通洞后直接跳出循环就行：

1
2
3
4
5
6
7
8
9
10
for(int i=0;i<top_count;i++){
    if(flag)break;
    for(int j=0;j<bottom_count;j++)
        if(find_u(u[top[i]]) == find_u(u[bottom[j]])){
            flag = true;
            break;
        }
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;

（5）完整代码实现

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
#include <iostream>
#include <cstdio>

using namespace std;

#define distance_sqrt(x1,x2,y1,y2,z1,z2) (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2)

int u[10005];
int top[100005];
int bottom[100005];
long long int x_pos[100005];
long long int y_pos[100005];
long long int z_pos[100005];

int find_u(int n)
{
    return n == u[n] ? n : (u[n] = find_u(u[n]));
}

void union_set(int a, int b)
{
    u[find_u(a)] = find_u(b);
}

int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        long long int n, h, r, r_sqrt_4, top_count = 0, bottom_count = 0;
        bool flag =  false;
        long long int x, y, z;
        scanf("%lld%lld%lld",&n,&h,&r);
        for(int i=1;i<=n;i++)u[i] = i;
        for(int i=1;i<=n;i++){            
            scanf("%lld%lld%lld",&x,&y,&z);x_pos[i] = x;y_pos[i] = y;z_pos[i] = z;
            if(z+r >= h)top[top_count++] = i;
            if(z-r <= 0)bottom[bottom_count++] = i;
            for(int j=1;j<i;j++)
                if(distance_sqrt(x_pos[j],x,y_pos[j],y,z_pos[j],z) <= r*r*4)
                    union_set(find_u(i),find_u(j));
        }
        for(int i=0;i<top_count;i++){
            if(flag)break;
            for(int j=0;j<bottom_count;j++)
                if(find_u(u[top[i]]) == find_u(u[bottom[j]])){
                    flag = true;
                    break;
                }
        }
        if(flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

0x03. 进阶：带权并查集

前面的亲戚关系是简单无向图，而且不带任何复杂数据记录，下面我们来看一道带权并查集的题目

例题：NOIP 2015 提高组 Day1 T2 - 信息传递（普及/提高-）

题目描述

来源：【洛谷P2661 [NOIP 2015 提高组] 信息传递】https://www.luogu.com.cn/problem/P2661

解题思路

玩家将自己的生日信息告知别人，并从别人那获取生日信息，首先自然还是图的连接，当存在信息传递时，我们便将节点进行连接，例如 1 号玩家向 2 号传递信息，我们便将 1 号与 2 号进行连接，形成一个图

但不同的是，我们这一次要求的并不仅是节点间是否存在关联关系，题目要求我们输出游戏一共可以进行多少轮

游戏什么时候停止呢？当有一个玩家接收到自己的信息时，也就是当图在连接过程中形成一个环时，这有点像我们的并查集的集合合并—— 我们可以使用并查集判断环，若是两个节点来自同一个集合，说明形成了一个环

环的最小长度如何判定呢？答案是 给并查集带上权值 ，在合并查找的过程当中 同步计算该节点到根节点的距离 ，这意味着在路径压缩的过程中我们并不像之前那样丢掉所有的路径信息，而是保留路径长度信息，我们可以使用一个额外的数组来存储， 题目要求的游戏轮数便是最短边的长度

（1）初始化元素集合

主要是两个数组，一个是基本的并查集，另一个是节点到根节点的距离（全都设为 0）：

1
2
3
4
5
6
7
8
9
10
11
int u[200005],d[200005]={0};
int min_len;

//...

int main(void)
{
    int n;
    min_len = 0xfffffff;
    cin >> n;
    for(int i=0;i<=n;i++)u[i] = i;

（2）建立关系：集合合并

反直觉的是每次读入输入其实就是需要我们进行集合合并的时刻：

1
2
3
4
5
6
7
8
int main(void)
{
    //...
    for(int i=1,x;i<=n;i++)
    {
        cin >> x;
        union_set(i,x);
    }

（3）搜索函数：找寻根节点 + 记录权值

如果节点不属于自身集合，递归查找其根节点，并一路记录路径长度：

1
2
3
4
5
6
7
8
int find_u(int n){
    if(u[n] != n){
        int last = u[n];
        u[n] = find_u(u[n]);
        d[n] += d[last];
    }
    return u[n];
}

（4）对比元素所属集合是否相同

如果两个元素属于同一集合， 说明此时形成了一个环 ，因此我们同步计算最短距离

1
2
3
4
5
6
7
8
9
10
void union_set(int a, int b){
    int x = find_u(a), y = find_u(b);
    if(x != y){
        u[x] = y;
        d[a] = d[b]+1;
    }
    else{
        min_len = min(min_len,abs(d[a]-d[b])+1);
    }
}

（5）完整代码实现

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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int u[200005],d[200005]={0};
int min_len;
int find_u(int n){
    if(u[n] != n){
        int last = u[n];
        u[n] = find_u(u[n]);
        d[n] += d[last];
    }
    return u[n];
}
void union_set(int a, int b){
    int x = find_u(a), y = find_u(b);
    if(x != y){
        u[x] = y;
        d[a] = d[b]+1;
    }
    else{
        min_len = min(min_len,abs(d[a]-d[b])+1);
    }
}
int main(void)
{
    int n;
    min_len = 0xfffffff;
    cin >> n;
    for(int i=0;i<=n;i++)u[i] = i;
    for(int i=1,x;i<=n;i++)
    {
        cin >> x;
        union_set(i,x);
    }
    cout << min_len << endl;
    return 0;
}

0x04. 进阶：带权并查集的综合应用场景

例题：NOI2002 银河英雄传说（普及+/提高）

题目描述

解题思路

  • 合并 && 查询->带权并查集
  • 三个数组：维护队列总长度
    维护不同战舰到队首长度​
    维护战舰归属队列

完整代码实现

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
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
int u[30005];
int dist[30005];
int num[30005];

int find_u(int n)
{
    if(u[n] != n)
    {
        int x = u[n];
        u[n] = find_u(u[n]);
        dist[n] += dist[x];
        num[n] = num[u[n]];
    }
    return u[n];
}

void union_set(int i, int j)
{
    int x = find_u(i);
    int y = find_u(j);
    if(x != y)
    {
        u[x] = y;
        dist[x] = dist[y] + num[y];
        num[y] += num[x];
        num[x] = num[y];
    }
}

int main(void)
{
    for(int i=0;i<=30005;i++)
    {
        u[i] = i;
        dist[i] = 0;
        num[i] = 1;
    }
    int t;
    scanf("%d", &t);
    while(t--)
    {
        char ch;
        int i,j;
        cin >> ch >> i >> j;
        int x = find_u(i);
        int y = find_u(j);
        if(ch == 'M')
        {
            union_set(i, j);
        }
        else
        {
            if(x != y)
                cout << -1 << endl;
            else
                cout << abs(dist[i]-dist[j]) - 1 << endl;
        }
    }
}

0x05. 进阶：有向图上的并查集应用

前面的大部分都是无向图，接下来我们来看一个有向图的上的并查集应用

例题：Leetcode 685. 冗余连接 II（困难）

题目描述

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1：

img

1
2
输入：edges = [[1,2],[1,3],[2,3]]
输出：[2,3]

示例 2：

img

1
2
输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出：[4,1]

提示：

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n

解题思路

半夜三点多把前置题：684. 冗余连接 给做了，感觉稍微有了点头绪，其实还是啥都不知道…

晚上大概想清楚了，同样是采用并查集的思想，不过考虑到该图为有向图，同时题目给定的图必定有且仅有一条多余的边使得该图无法成为一颗树

可能存在如下情况：

  • 一个节点的入度大于等于2（存在两个及以上父结点，本题数据构造保证只可能存在两个父结点的情况）
  • 图中存在回路
  • 以上两种情况同时存在

如下图所示（字丑见谅QwQ）：

故我们很容易（并不Or2）能够得到解开这道题的算法：

  • 将每一个结点初始化为一棵单独的树，其父结点初始化为自身
  • 使用两个数组分别保存每个结点的父结点与所属的树的根结点
  • 遍历每一条边，重新记录下每个结点的父结点与根节点
  • 当一个结点的入度大于1时（出现第二个不是自身结点的父亲），记录该边为争议边
  • 当一条边的始末结点同属于一棵树时，记录该条边为回路边
  • 两种情况都不存在，则将该边的末结点的父结点标为该边的始结点，并合并两结点所在的树
  • 当争议边不存在时，直接删除回路边
  • 争议边若存在，若同时存在回路边，则删除争议边末尾结点及其父结点所构成边，否则删除争议边

（1）初始化元素集合

还是按惯例将每个节点单独作为一棵树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int * ancestors;//（并查集）记录每个节点的根结点
int * parent;//记录每个节点的父结点

//...

int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    ancestors = (int*)malloc(sizeof(int)*(edgesSize+5));
    parent = (int*)malloc(sizeof(int)*(edgesSize+5));

    for(int i=1;i<=edgesSize;i++)
    {
        parent[i] = ancestors[i] = i;//初始化每个结点为单独的一棵树（并查集），结点的父结点标记为自身
    }

（2）建立关系：集合合并 + 记录异常

我们遍历每一条边，从而逐渐连接起各个节点，建立起集合，在合并集合的过程中同时查找我们的两种冲突情况：

  • 边的首尾节点的根节点相同，说明可能存在回路
  • 边的尾节点与其他节点相连，说明存在入度大于一的节点
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
//conflict：可能存在争议的边
   //circle：可能形成回路的边
   int start, end, a_start, a_end, conflict = -1, circle = -1;

   for(int i=0;i<edgesSize;i++)
   {
       start = edges[i][0];
       end = edges[i][1];
       a_start = find_x(start);
       a_end = find_x(end);
       if(parent[end] != end)//该条边的尾结点已经与其他结点相连（即加上这条边后入度大于1）
       {
           conflict = i;//记录该条边为争议边
       }
       else
       {
           parent[end] = start;
           if(a_start == a_end)
           {
               circle = i;//该条边两结点的根结点相同，可能形成回路
           }
           else
           {
               union_ancestor(start, end);//将两棵树合并为一棵树（并查集）
           }
       }
   }

（3）搜索函数与合并函数

这一块倒是比较常规的路径压缩：

1
2
3
4
5
6
7
8
9
int find_x(int x)//查找该结点所属树的根结点
{
    return x == ancestors[x] ? x : (ancestors[x] = find_x(ancestors[x]));//路径压缩
}

void union_ancestor(int a, int b)
{
    ancestors[find_x(a)] = find_x(b);//将两棵树合并为一棵树
}

（4）完整代码实现

构造代码如下：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 /**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int * ancestors;//（并查集）记录每个节点的根结点
int * parent;//记录每个节点的父结点

int find_x(int x)//查找该结点所属树的根结点
{
    return x == ancestors[x] ? x : (ancestors[x] = find_x(ancestors[x]));//路径压缩
}

void union_ancestor(int a, int b)
{
    ancestors[find_x(a)] = find_x(b);//将两棵树合并为一棵树
}

int* findRedundantDirectedConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize)
{    
    ancestors = (int*)malloc(sizeof(int)*(edgesSize+5));
    parent = (int*)malloc(sizeof(int)*(edgesSize+5));

    for(int i=1;i<=edgesSize;i++)
    {
        parent[i] = ancestors[i] = i;//初始化每个结点为单独的一棵树（并查集），结点的父结点标记为自身
    }
	//conflict：可能存在争议的边
    //circle：可能形成回路的边
    int start, end, a_start, a_end, conflict = -1, circle = -1;

    for(int i=0;i<edgesSize;i++)
    {
        start = edges[i][0];
        end = edges[i][1];
        a_start = find_x(start);
        a_end = find_x(end);
        if(parent[end] != end)//该条边的尾结点已经与其他结点相连（即加上这条边后入度大于1）
        {
            conflict = i;//记录该条边为争议边
        }
        else
        {
            parent[end] = start;
            if(a_start == a_end)
            {
                circle = i;//该条边两结点的根结点相同，可能形成回路
            }
            else
            {
                union_ancestor(start, end);//将两棵树合并为一棵树（并查集）
            }
        }
    }

    int *ret = (int*)malloc(sizeof(int)*2);
    *returnSize = 2;
    if(conflict<0)//不存在争议边，只存在形成回路的边
    {
        ret[0] = edges[circle][0];
        ret[1] = edges[circle][1];
        return ret;
    }
    else//存在争议边
    {
        if(circle>0)//同时存在回路边
        {
            ret[0] = parent[edges[conflict][1]];
            ret[1] = edges[conflict][1];
            return ret;
        }
        else
        {
            ret[0] = edges[conflict][0];
            ret[1] = edges[conflict][1];
            return ret;
        }
    }
    return ret;
}

0xFF. 更多相关题目

POJ2236: http://poj.org/problem?id=2236

ALGORITHM
#C&C++ #Algorithm #Disjoint Set
【ALGORITHM.0x00】并查集算法浅析
https://arttnba3.github.io/2019/09/20/ALGORITHM-0X00-DISJOINT_SET/
作者
arttnba3
发布于
2019年9月20日
许可协议