[Acwing] 基础算法（七) 并查集

并查集

算法思路

使用场景

将两个集合进行合并
询问两个元素是否在一个集合中

我们很简单的可以想到判断两个元素是否在一个集合中可以使用map进行 o1 的判断，但是对于合并集合无法避免是 o(n) 的

因此我们考虑使用树的形式存储集合

对于一个集合，其根节点代表整个集合编号
使用 p[x] 表示其父节点

对于一个单边集合

1

1 → 2 → 3 → 4

我们如果要找到 1 的集合，那么需要从 p[1],p[2],p[3]一直寻找

但是我们可以考虑进行优化，对于找到根节点的集合，我们将其全部转移到根节点，即路径压缩

1
2
3


1 ──┐
2 ──┼──→ 4
3 ──┘

代码

其中 p[x] = find(p[x]) 代表路径压缩

 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


int p[N] ;

int find(int x) {
    if(p[x]!= x) {
        return p[x] = find(p[x]);
    }
    return p[x];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n,m;cin>>n>>m;
  for(int  i = 1 ; i <= n ; i ++ ) {
     p[i] = i ;
  }
  for(int i = 1 ; i <= m ; i ++ ) {
    char op;cin>>op ;
    int a,b;cin>>a>>b;
    int fa = find(a);
    int fb = find(b);
    if(op == 'M') {
        p[fa] = fb;
    }else if(op == 'Q') {
        if (fa == fb) {
            cout<<"Yes"<<endl;
        }else {
            cout<<"No"<<endl;
        }
    }
  }
}