并查集模板

并查集主要是用于解决元素合并以及元素查询类问题，在这种问题种，是以树的形式将

多个元素连接起来，一个树代表了一个集合。这是一种以空间换时间的做法。在后续进

行过程中可能会导致许多元素形成一个单链形式的结构，这样查询的时候就会浪费很多

时间，因此又对这种情况做出了路径压缩的算法，在代码中会提到。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 100010;
 6 int fa[N];
 7 int find(int x){    //并查集核心，包括查找所属集合以及路径压缩
 8     if(x != fa[x]) fa[x] = find(fa[x]);  //使用递归求当前点的祖先，顺便将当前节点直接连到祖先节点
 9     return fa[x];  //当找到这个点的祖先节点时也就是找到了所属集合，返回集合答案
10 }
11 int main(){
12     int n, m;
13     cin >> n >> m;
14     for(int i = 1; i <= n; i ++) fa[i] = i; //初始化，先让每个节点是自己的父节点（形成自环）
15     char op[2];
16     while(m --){
17         int a, b;
18         cin >> op;
19         cin >> a >> b;
20         if(op[0] == 'M')
21             if(find(a) != find(b))
22                 fa[find(a)] = find(b); //如果两个不是一个集合，那么让a的父节点成为b的子节点
23         if(op[0] == 'Q'){
24             if(find(a) == find(b)) cout << "YES" << endl;
25             else cout << "NO" << endl;
26         }
27     }
28     return 0;
29 }