合并集合

/*
 * @Author: YMYS
 * @Date: 2025-03-12 22:08:31
 * @LastEditTime: 2025-04-10 21:05:54
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\2.第二章\9.并查集\1.合并集合.cpp
 * @URL:https://www.acwing.com/problem/content/838/
 * @Description: 836. 合并集合
 * 
 * 并查集基本模板
 * 
 */
#include<bits/stdc++.h>

#define int long long
#define err cout << "error" << endl

using namespace std;

const int N = 1e5 +10;

// int T;
// void solve(){

// }
int  n,m;
int p[N];//p[i]表示i的父亲节点

//find(x)函数：查找x的根节点 + 路径压缩
//时间复杂度接近O(1)
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

signed main()
{
#ifdef ABC
    freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
    freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

    // cin>>T;
    // while(T--){
    //     solve();
    // }
    cin>>n>>m;

    //初始化并查集，每一个节点的父亲节点都是其自己
    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }

    for(int i=0;i<m;i++){
        char c;
        int a,b;
        cin>>c>>a>>b;

        if(c == 'M'){
            p[find(a)] = find(b);//a的根节点的父亲节点，变成b的根节点【//集合合并操作】
        }else{
            if(find(a) == find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }

    return 0;
}

连通块中的点的数量

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define vector <pair<int, int>> PII

const int N = 100010;

int n, m;
int q[N], size_q[N];

int head(int x) // 找x的祖宗结点（实际上为根结点）+缩短路径（缩短x到q[x]的路径）
{
    if (q[x] != x)
        q[x] = head(q[x]); // q[x]==x，表示x点是根结点
    return q[x];
}

signed main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>m;

    for (int i=1;i<=n;i++){
        q[i] = i;
        size_q[i] = 1;
    }

    while (m--){
        int a,b;
        char s[5];

        cin>>s;

        if (s[0]=='C'){ 
            cin>>a>>b;
            if (head(a)==head(b)) continue;

            size_q[head(b)] += size_q[head(a)];
            q[head(a)]=head(b); // 让a所属树的根节点的父亲结点，为b的根结点
        }else if (s[1]=='1'){
            cin>>a>>b;
            if (head(a)==head(b))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }else{
            cin>>a;
            cout<<size_q[head(a)]<<endl;
        }
    }
    return 0;
}

食物链【带权并查集】

/*
 * @Author: YMYS
 * @Date: 2024-01-27 20:29:17
 * @LastEditTime: 2025-03-17 21:47:46
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\2.第二章\9.并查集\3.食物链.cpp
 * @URL:https://www.acwing.com/problem/content/242/
 * @Description: 240. 食物链
 * 
 * 带权并查集
 * 
 * 
 * 
 */
#include<bits/stdc++.h>

#define int long long
#define err cout << "error" << endl

using namespace std;

const int N = 5e4 + 10;
const int M = 1e5 + 10;

// int T;
// void solve(){

// }

int n,k;
int p[N];//p[i]表示i点的父亲节点是p[i]
int d[N];//d[i]表示i点到父亲节点的距离。【余数表示谁吃谁：0吃1，1吃2，2吃0】【也可以是2吃1，1吃，0吃2（代码写好就可以）】
int res;//假话总数

//find(x)函数返回的是点x所在的这棵树的根节点
//在执行过程中会执行路径压缩，会把每个点的父亲节点更新为根节点
int find(int x)
{
    if(p[x] != x){
        //执行完下面这行语句后，p[x]的父亲节点就是根节点了
        //并且t就是根节点的值
        int t = find(p[x]);

        //d[x]本身是x到旧父亲节点的距离，
        //后续我们要把x的父亲节点更新为根节点，所以我们现在先把d[x]更新为x到根节点的距离
        d[x]+=d[p[x]];

        //更新x的父亲节点为根节点
        p[x] = t;
        //p[x] = find(p[x]);
    }

    return p[x];
}



signed main()
{
#ifdef ABC
    freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
    freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
#endif
    std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

    // cin>>T;
    // while(T--){
    //     solve();
    // }
    cin>>n>>k;
    //初始化并查集数组
    for(int i=1;i<=n;i++) p[i]=i;

    while (k--)
    {
        int c,x,y;
        cin>>c>>x>>y;

        int cx = find(x), cy = find(y);
        //在执行完find函数后，x和y的父亲节点就是根节点了

        if(x>n || y>n) res++;
        else if(c == 1){
            //这里的判断条件处理的是：
            //1、x和y处于同一棵树
            //2、d[x]和d[y]对3的余数相同，即x和y需是同一类
            if(cx == cy && (d[x] - d[y])%3 != 0) res++;
            else if(cx != cy){
                //dx != dy --> x和y不在同一个树，也说明了这句话是真话
                //接下来拼接这两棵树，把x和y是同类的情况记录下来即可
                p[cx] = cy;
                d[cx] = d[y] - d[x];//(d[x]+d[px]-d[y])%3==0【因为得是同类】

                //////////////////////////////////d[y]<d[x]会怎么样



            }else{
                //x和y在同一个树，并且他们是同一类
                //那就不用管
            }

        }else if(c == 2){
            if(x==y) res++;
            //x吃y的话，说明d[x]比d[y]大1，其实也可以是d[x]比d[y]小1
            //至于我们的树从空树开始存【x吃y】的时候，
            //他存的是x比y大1还是存的y比x大1.其实无所谓，
            //我们把对应代码写好就可以了。
            else if(cx == cy && (d[x] - d[y] - 1)%3 != 0) res++;
            else if(cx != cy){//x吃y，x和y还不是同一棵树
                //此时，我们就需要合并两棵树木
                p[cx] = cy;
                d[cx] = d[y] - d[x] + 1;//(d[x] + d[cx] - d[y] - 1)%3==0 【因为x吃y，x比y大1】



            }
        }
    }



    cout<<res<<endl;



    return 0;
}