并查集(union-find set )

适用组别：提高组
难度系数：6

OJ:P1846/P1850

一、集合(set)：

集合是由一个或多个确定的元素所构成的整体。集合中的元素有如下三个特征：
1、确定性：一个元素要么属于集合，要么不属于集合。
2、互异性：集合中的元素互不相同。
3、无序性：集合中的元素没有先后顺序。

二、并查集(union-find set)：

并查集是一个可以维护集合的数据结构，它能高效支持集合的基本操作。
1、合并两个集合
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/****************************************************************
 * C++  并查集
 * date: 2023-6-3
 * author: Alex Li
 * version: 1.2
 * ****************************************************************/
#include <iostream>
using namespace std;


int father[200];
int x,y;
//找x的祖先，通过递归，当到达祖先位置时，返回祖先
int find(int x){
    //不断向上查找祖先
    if(father[x]!=x) return find(father[x]);
    //路径压缩，所有结点指向一个祖先
    //if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
//合并祖先
void unionn(int r1,int r2){
    father[r2]=r1;
    }

bool judge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return true;
    else return false;
}

int main(){
    int n,m;
    cin>>n>>m;
    //初始化，每个结点的父结点都试成自己
    for (int i = 1; i <= n; i++)father[i]=i;
    
    
    for (int i = 1; i <= m; i++){
        cin>>x>>y;
        int r1=find(x);
        int r2=find(y);
        if(r1!=r2)unionn(r1,r2);
    }
    cin>>x>>y;
     if(judge(x,y))cout<<"YES";
     else cout<<"NO";
}

求连通分量数和最大连通分量

 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
/****************************************************************
 * 代码作者: Alex Li
 * 创建时间: 2026-05-16 13:50
 * 最后修改: 2026-05-16 13:50
 * 文件描述: 并查集算法示例，动态维护无向图的连通分量个数与最大连通块大小，时间复杂度接近 O(m alpha(n))
 * 核心算法: 使用路径压缩和按大小合并维护集合，边加入时合并端点所在集合并更新答案
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;

int parent[MAXN], sz[MAXN];
int n, m, components;

// 初始化并查集：开始时每个点单独成一个集合。
void initialize() {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

// 查找 a 所在集合的根，并进行路径压缩。
int findRoot(int a) {
    if (parent[a] == a) {
        return a;
    }
    return parent[a] = findRoot(parent[a]);
}

// 合并 a 和 b 所在的集合。
// 如果原本属于不同集合，连通分量个数减 1。
void mergeSet(int a, int b) {
    a = findRoot(a);
    b = findRoot(b);
    if (a == b) {
        return;
    }

    --components;

    // 按大小合并：把小集合挂到大集合下面，避免树退化过高。
    if (sz[a] > sz[b]) {
        swap(a, b);
    }
    parent[a] = b;
    sz[b] += sz[a];
}

// 返回 a 所在连通块的大小。
int findSize(int a) {
    return sz[findRoot(a)];
}

int main() {
    cin >> n >> m;
    initialize();

    components = n;
    int maxComponentSize = (n > 0 ? 1 : 0);

    // 输入格式：
    // n m
    // 接下来 m 行，每行一条无向边 a b，默认结点编号为 0 ~ n-1。
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        mergeSet(a, b);
        maxComponentSize = max(maxComponentSize, findSize(a));

        // 输出当前连通分量个数，以及当前最大连通块大小。
        cout << components << " " << maxComponentSize << "\n";
    }

    return 0;
}

练习题：见二分图P1525

NOIP2010_S_3
Previous Topic
Back to Lesson
Next Topic