并查集（路径压缩）

并查集：
1.将两个集合合并
2.查询两个元素是否在一个集合当中
基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储他的父节点，p[x]表示x的父节点
问题1：如何判断树根？if(p[x] == x)
问题2：如何求x的集合编号？while(p[x] != x) x = p[x]
问题3：如何合并两个集合编号，py是y的集合编号，p[x] = y
优化：路径压缩

例题：

#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 == 'M') p[find(a)] = find(b);//集合合并操作
        else
        {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    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

并查集：
在刚开始的时候，每个集合都是一个独立的集合，都只有一个数，并且集合都是等于自己本身下标的数；
例如：p[1] = 1; p[50] = 50;
如果是M操作（合并）的话，就是将 p[3] = p[5];此时集合3就被纳入到集合5里面了，称为了集合5的子集；
所以3的祖宗节点就变成了5，此时以5为祖宗节点的集合为{5,3}
如果要将集合6插入到集合3当中，就要找到集合3的祖宗节点
所以 p[6] = p[3]，也就可以 p[find(6)] = find(3)
因为6的祖宗节点本来就是6，此时以5为祖宗节点的集合就为{5,3，6}

路径压缩：