并查集

发表于 分类于 阅读次数： 本文字数： 843 阅读时长 ≈ 3 分钟

【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 ,表示共有 个元素和 个操作。

接下来 行，每行包含三个整数 。

当 时，将 与 所在的集合合并。

当 时，输出 与 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出 #1

1
2
3
4
N
Y
N
Y

提示

对于 的数据，，。

对于 的数据，，。

对于 的数据，，。

对于 的数据，，，，。

题解

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
#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
struct dsu{
    vector<int> parent,size;
    //Single-argument constructors must be marked explicit to avoid unintentional implicit conversions
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
    // 查询
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    // 启发式合并
    void unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y)
            return;
        if(size[x]<size[y])
            swap(x,y);
        parent[y]=x;
        size[x]+=size[y];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    dsu s=dsu(n);
    int x,y,z;
    for(int i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1){
            s.unite(x,y);
        }
        else{
            if(s.find(x)==s.find(y)){
                cout<<'Y'<<endl;
            }
            else{
                cout<<'N'<<endl;
            }
        }
    }
    return 0;
}

并查集介绍

并查集是一种数据结构，用于处理一些不交集合并及查询的问题。
并查集是森林，每个集合用一个树结构表示，树的根节点代表整个集合。

结构

1
2
3
4
5
6
7
8
struct dsu{
    vector<int> parent,size;
    // 单参数构造函数必须使用 explicit 关键字进行标记，以避免发生不必要的隐式类型转换。在<numeric>库里
    //这里节点是从1开始到s
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
};

合并

动画

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 简单合并
void simple_unite(int x, int y) {
    parent[find(x)] = find(y);
}
// 启发式合并
void unite(int x,int y){
    x=find(x),y=find(y);
    if(x==y)//在同一个集合里
        return;
    if(size[x]<size[y])
        swap(x,y);
    parent[y]=x;
    size[x]+=size[y];
}

查询

动画

找到了根节点，就顺便把父节点都更新成根节点

1
2
3
int find(int x){
    return parent[x]==x?x:parent[x]=find(parent[x]);
}

删除

1
2
3
4
void erase(int x) {
    --size[find(x)];
    parent[x] = x;
}

移动

1
2
3
4
5
6
void move(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    parent[x] = fy;
    --size[fx], ++size[fy];
}

总代码

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
struct dsu{
    vector<int> parent,size;
    explicit dsu(int s):parent(s+1),size(s+1,1){
        iota(parent.begin(),parent.end(),0);//1,2,...,s-1
    }
    // 查询
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    // 合并
    void simple_unite(int x, int y) {
        parent[find(x)] = find(y);
    }
    // 启发式合并
    void unite(int x,int y){
        //找到根结点
        x=find(x),y=find(y);
        //在同一个集合里
        if(x==y)
            return;
        if(size[x]<size[y])
            swap(x,y);
        parent[y]=x;
        size[x]+=size[y];
    }
    //删除
    void erase(int x) {
        --size[find(x)];
        parent[x] = x;
    }
    //移动
    void move(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        parent[x] = fy;
        --size[fx], ++size[fy];
    }
};