Fork me on GitHub

并查集

发表于 | 分类于 | 次阅读
字数统计: 237 | 阅读时长 ≈ 1

基本代码

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

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> parent;
int Find(int x){      // 并查集的查找父亲节点函数
    int origin = x;
    while(x != parent[x]){
        x = parent[x];
    }
    parent[origin] = x;        // 查找的过程中顺便路径压缩
    return x;
}

void to_union(int x1 , int x2){  // 将两个节点合并
    int p1 = Find(x1);
    int p2 = Find(x2);
    parent[p2] = p1;
}

bool isSame(int x1 , int x2){    // 判断两个节点的父亲节点是不是相同
    return Find(x1) == Find(x2);
}

int main()
{

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>n;
    for(unsigned int i = 0 ; i<n ; ++i){
        parent.push_back(i);               // 初始化每个节点的父亲节点是自己
    }
    int u , v;
    int m;
    cin>>m;
    for(int i = 0 ; i<m ; ++i){
        cin>>u>>v;
        to_union(u , v);
    }
    for(int i = 0 ; i<n ; ++i){
        Find(i);                  // 每个节点都路径压缩
    }
    for(int i = 0 ; i<n ; ++i){
        cout<<parent[i]<<' ';
    }
}