并查集

一、算法用途

二、算法实现

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
#include <cstdio>
#define MAXN 5005
int fa[MAXN], rank[MAXN];
vector<int>fa1;
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;//父节点，或者说所在的集合的标志
        //rank[i] = 1;记录深度
    }
}
void init(n):fa1(n){
    iota(fa1.begin(),fa1.end(),0);
}
int find(int x)//查询x所在哪个集合
{
    if (fa[x]==x)
        return x;
   	else
        return find(fa[x]);
}
int find2(int x)//路径压缩
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点//一次只能压缩一层
        return fa[x];         //返回父节点
    }
    //return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
/*
inline void merge(int i, int j)
{
    fa[find(i)] = find(j);//将后一个的父节点同时给前一个节点的父节点，即将其老大更换
}
*/
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    //我们将拥有更多子节点父亲的作为拥有更少节点的
    //类似于大的吃掉小的，这样小弟不能造成更大的麻烦
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
    if(x!=y)
        --count;//合并问题选项
}
// 通常使用以下的合并方式
inline void merage(int i, int j){
    int x = find(i) , y = find(j);
    if(x!=y) fa[x] = y, count--;
}
bool connected(int a ,int b){
    return find(a) == find(b);
}
//关于求集合个数问题，定义全局变量，合并一个减一个

//将所有一个集合的合并找到同一个祖先
void end(){
    for(int i = 0; i < n; ++i) fa[i] = find(i);
}
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
class UF{
public:
    vector<int>fa;
    vector<int>rank;
    int n;
    int comp_cnt;
public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), rank(_n, 1){
        iota(fa.begin(),fa.end(),0);
    }
    int find(int x){
        //cout << "find" << endl;
        return x==fa[x] ? x:(fa[x] = find(fa[x]));
    }
    inline void merage(int i, int j){
        int x = find(i);
        int y = find(j);
        if (rank[x] <= rank[y])
            fa[x] = y;
        else
            fa[y] = x;
        if (rank[x] == rank[y] && x!=y)
            rank[y]++;
    	if (x!=y)
            comp_cnt--;
    }
    bool connected(int x,int y){
        x = find(x);
        y = find(y);
        return x==y;
    }
};

并查集与带权并查集—-由浅入深 - Gribouillage - 博客园 (cnblogs.com)

带权值的并查集