并查集.md

并查集

常用操作：

1. 合并两个集合
2. 询问两个元素是否在一个集合中

算法原理：每个子集合用一颗树来表示，所有表示子集合的树构成表示全集合的森林；通常用数组元的下标来表示元素名，用根结点的下标表示整个子集合

//836.合并集合(ACWing)
//一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m 个操作，操作共有两种：
//1.M a b将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
//2.Q a b询问编号为 a 和 b 的两个数是否在同一个集合中；

#include <iostream>

using namespace std;

const int N = 100010;
int s[N];

int Find(int x)         //返回祖先节点 + 路径压缩
{
    if(s[x] != x)
        s[x] = Find(s[x]);
    return s[x];
}

int main()
{
    int n , m;
    cin >> n >> m;
    
    for(int i = 1 ; i <= n ; i ++)	//初始化每个元素，每个元素的根结点均是自己
        s[i] = i;
    
    while(m --)
    {
        char q;
        int a , b;
        cin >> q >> a >> b;
        if(q == 'M')
            s[Find(a)] = Find(b);	
            
        else
        {
            if(Find(a) == Find(b))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }
    return 0;
}

合并两个集合：

s[Find(a)] = Find(b);	

让元素a的祖先节点的父节点等于b的祖先结点

查找两个元素是否在同一个集合

int Find(int x)         //返回祖先节点 + 路径压缩
{
    if(s[x] != x)
        s[x] = Find(s[x]);
    return s[x];
}

这里对算法进行了优化（路径压缩），将集合中的每个元素所对应的数组中的元素都设为了该集合的根结点，这样可以在*O(1)*的时间内找到一个元素所在的集合，以下是未经优化的代码：

int Find(int x)
{
    while(s[x] != x)
        x = s[x];
    return x;
}

该算法需要一步步找该元素的父节点，直至找到祖先节点

---

//837. 连通块中点的数量(ACWing)
//给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。现在要进行 m 个操作，操作共有三种：
//1.C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
//2.Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
#include <iostream>

using namespace std;

const int N = 100010;
int s[N] , num[N];

int Find(int x)
{
    if(s[x] != x)
        s[x] = Find(s[x]);
    return s[x];
}

int main()
{
    int n , m;
    cin >> n >> m;
    
    for(int i =0 ; i < n ; i ++)
    {
        s[i] = i;
        num[i] = 1;
    }
    
    while(m --)
    {
        string q;
        int a , b;
        cin >> q;
        
        if(q == "C")
        {
            cin >> a >> b;
            if(Find(a) == Find(b))
                continue;
            num[Find(b)] += num[Find(a)];
            s[Find(a)] = Find(b);
        }
        
        else if(q == "Q1")
        {
            cin >> a >> b;
            if(Find(a) == Find(b))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
        
        else
        {
            cin >> a;
            cout << num[Find(a)] << endl;
        }
    }
    return 0;
}

在更新num数组时，需要先更新num数组再进行集合的合并，否则num数组得到的就是合并后的数组的2倍大小，产生逻辑上的错误

//不能颠倒
num[Find(b)] += num[Find(a)];
s[Find(a)] = Find(b);