并查集模板及思想

acwing相关资料：https://www.acwing.com/activity/content/problem/content/885/

基本思想

如果想合并两个集合，直接把根节点插到另一个集合的某个地方即可

路径压缩优化–时间复杂度近乎为O(1)

在问题2中，求x的集合编号与数的高度成正比，复杂度较高，所以可以进行优化，在第一次查的时候正常一步一步查到根节点while(p[x]!=x) x=p[x]，但一旦找到后就会把这个线上的所有点都指向根节点，之后再查就是O(1)的复杂度

代码

模板题：https://www.acwing.com/problem/content/838/

#include 
using namespace std;
const int N = 100010;
int p[N];
int find(int x) // 返回祖宗节点+路径压缩
{
    // 如果不是根节点则进行路径优化
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main() 
{
    int n,m;
    scanf("%d%d",&n,&m);
    //初始化
    for(int i = 1; i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        // 将根节点的父节点改为另一个集合的父节点完成合并操作
        if(op[0] == 'M') p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}
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

拓展维护集合额外信息

维护集合个数

:::info
例题：https://www.acwing.com/activity/content/problem/content/886/
:::

#include 
using namespace std;
const int N = 100010;
int p[N],cnt[N];

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    // 初始化
    for (int i = 1; i <= n; i++) 
    {
        p[i] = i;
        cnt[i] = 1;
    }
    
    while(m--) 
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C') 
        {
            scanf("%d%d",&a,&b);
            a = find(a);
            b=find(b);
            if (a!=b){
                p[a] = b;
                cnt[b]+=cnt[a];
            } 
            
        }else{
            if (op[1] == '1') 
            {
                scanf("%d%d",&a,&b);
                if(find(a)==find(b))
                    cout<<"Yes"<<endl; 
                else 
                    cout<<"No"<<endl; 
            }else{
                scanf("%d",&a);
                cout<<cnt[find(a)]<<endl;
            }
                
        }
    }
    return 0;
}
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