并查集

本文主要是介绍并查集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <iostream>

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;
}

pta天梯模拟中的并查集题目：

（可能写得不太好qwq~）

#include <bits/stdc++.h>
using namespace std;
const int N=100000;
int p[N],k[N],cnt[N];
int Find(int x)
{
    if (p[x]!=x)p[x]=Find(p[x]);
    return p[x];
}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=10001;i++)
    {
        p[i]=i;
    }
    long long sum=0;
    while (n--)
    {
        int num;
        cin>>num;
        for (int i=1;i<=num;i++)
        {
            cin>>k[i];
            cnt[k[i]]++;
            if (i>1)
            {
                p[Find(k[i])]=Find(k[i-1]);
            }
        }
    }
    long long tot=0;
    for (int i=1;i<=10001;i++)
    {
        if (cnt[i])sum++;
        if (cnt[i]&&p[i]==i)tot++;
    }
    int q;
    cout<<sum<<' '<<tot<<"\n";
    cin>>q;
    while (q--)
    {
        int s,l;
        cin>>s>>l;
        if (Find(s)==Find(l))puts("Y");
        else puts("N");
    }
    return 0;
}

这篇关于并查集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！