并查集

并查集（Union-find)：

首先看一下查找的过程，两行代码：

//查找x元素所在集合的编号
int find(x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

if(find(x) != find(y)) p[find(x)] = find(y);//合并

for(int i = 0;i<n;i++) p[i] = i; p[0] = 0, p[1] = 1, p[3] = 3, p[5] = 5;

举个例子：比如有5、3、1、0四个数字来合并的话,

p[find(5)] = find(3) = 3, p[find(3)] = find(1) = 1, p[find(1)] = find(0) = 0;

p[5] = 3, p[3] = 1, p[1] = 0; p[0] = 0 = 0;

我们再来看这两行代码：if(x != p[x]) p[x] = find(p[x]); return p[x];

5 != p[5]=3, 3!=p[3], p[3] = find(p[3]) = 1, 1 != p[1], p[1] = 0 = find(0), 但是0 = p[0] = 0的, 所以直接return p[x] = 0;

 例题：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
初始的时候p[1] = 1, p[2] = 2, p[3] = 3, p[4] = 4;
合并1和2，即：p[find(1)] = find(2);
合并3和4，即：p[find(3)] = find(4);

判断的时候就是find(1) p[1] = 2 = find(2) , 2 = p[2], return 2 find(1) = find(2) = 2;

所以1和2 是属于同一个集合。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int p[N];
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i = 0;i<n;i++) p[i] = i;
    while(m--)
    {
        char op;int a,b;
        cin>>op;
        if(op == ‘M‘)
        {
            cin>>a>>b;
            p[find(a)] = find(b);
        }
        else if(op == ‘Q‘)
        {
            cin>>a>>b;
            if(find(a) == find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
}

并查集

原文：https://www.cnblogs.com/longxue1991/p/12687749.html