并查集

题目传送门

并查集板题

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lll __int128
#define Mio_qh signed
#define el '\n'
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pq priority_queue
const int MOD = 998244353;
const int N = 200721;

int fastpow(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = (base*result)%MOD;
        exp >>= 1;
        base = (base*base)%MOD;
    }
    return result;
}
int hx[8]={1,1,-1,-1,2,-2,2,-2};
int hy[8]={2,-2,2,-2,1,1,-1,-1};

void print(lll x) {
    if(x==0) cout<<0<<el;
    else {
        string ans="";
        while(x!=0) {
            int t=x%10;
            ans=to_string(t)+ans;
            x=x/10;
        }
        cout<<ans<<el;
    }
}
vector<int> father(N);

int find(int x) {
    if (x!=father[x]) father[x]=find(father[x]);
    return father[x];
}
bool issame(int a,int b) {
    return find(a)==find(b);
}

void uoionset(int a,int b) {
    a=find(a);
    b=find(b);
    if(a!=b) {
        father[a]=b;
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) father[i]=i;
    while (m--) {
        int c,x,y;
        cin >> c >> x >> y;
        if (c==1) uoionset(x,y);
        else {
            if (issame(x,y)) cout<<"Y"<<el;
            else cout<<"N"<<el;
        }
    }
}


Mio_qh main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;  //多测
    while (tt--) solve();
}