目录

acwing基础课ch2-并查集

Shen 收录于算法基础课

2021-08-24 约 684 字预计阅读 2 分钟

目录

并查集

并查集是什么

Union,Find,Set

并查集包含Union,Find,Set3个关键词，是一种维护集合的基本操作。
并查集是一种用树表示的集合，树根的编号表示集合的编号。

并查集实现的方法

并查集由两个任务：
合并：合并两个集合。
查找：判断两个元素是否在一个集合内。
实现：数组实现，索引表示结点编号，数组的值表示索引的根节点。同一个集合中只能包含一个根节点(father[i] = i)。

查找父节点

1
2
3
4
5
6


int findFather(int x, int father[]){
    while(x != father[x]){
        x = father[x];
    }
    return x;
}

合并结点
- 一定要使用根节点进行合并。
- 查找它们的根节点，如果他们根节点不同，则属于不同的集合才可以进行合并。

1
2
3


void Union(int a, int b, int fa[]){
	fa[find(a)] = find(b);
}

路径压缩
- 把当前查询结点的路径上所有节点的父亲都指向根节点。

1
2
3
4


int find(int x, int fa[]){
	if(x != far[x])	fa[x] = find(fa[x]);
    return fa[x];
}

写法

静态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int fa[N];

// 初始化
for(int i = 1; i <= n; i++){
    fa[i] = i;
}

// find
int find(int x){
	if(x = fa[x])	return x;
    f[x] = find(f[x]);
    return f[x];
}
// 合并
void Union(int x){
    fa[find(x)] = find(y);
}
// 查询
int qury(int x, int y){
    return find(y) == find(y);
}

OOP

 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


const int N = 1e5+10;

class UnionFindSet{
  private:
  vector<int> f;
  public:
  UnionFindSet(int n = N){
      f = vector<int>(n + 1, 0);
      for(int i = 1; i <= n; i++){
          f[i] = i;
      }
  }
  int find(int x) {
      if(x != f[x]) f[x] = find(f[x]);
      return f[x];
  }
  
  void un(int x, int y) {
      f[find(x)] = find(y);
  }
  
  bool qury(int x, int y) {
      return find(x) == find(y);
  }
  
};

Ac836.合并集合

 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


#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5+10;

class findUnionSet{
  private:
  vector<int> f;
  public:
  findUnionSet(int n = N){
      f = vector<int>(n + 1, 0);
      for(int i = 1; i <= n; i++){
          f[i] = i;
      }
  }
  int find(int x) {
      if(x != f[x]) f[x] = find(f[x]);
      return f[x];
  }
  
  void un(int x, int y) {
      f[find(x)] = find(y);
  }
  
  bool qury(int x, int y) {
      return find(x) == find(y);
  }
  
};

int main(){
    int n, m;
    cin >> n >> m;
    
    findUnionSet myun;
    
    while(m--){
        char op;
        int x, y;
        cin >> op >> x >> y;
        if(op == 'M'){
            myun.un(x, y);
        }
        else{
            if(myun.qury(x, y))  cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    
    return 0;
}