题解 | #【模板】并查集#

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n; vector<int> fa, sz;
    DSU(int n): n(n), fa(n+1), sz(n+1, 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x){ return fa[x]==x? x : fa[x]=find(fa[x]); }
    void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(sz[a]<sz[b]) swap(a,b); fa[b]=a; sz[a]+=sz[b]; }
    int size(int x){ return sz[find(x)]; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; if(!(cin>>n>>m)) return 0;
    DSU dsu(n);
    string out; out.reserve(m*4);
    for(int i=0;i<m;++i){
        int op; cin>>op;
        if(op==1){ int x,y; cin>>x>>y; dsu.unite(x,y); }
        else if(op==2){ int x,y; cin>>x>>y; out += (dsu.find(x)==dsu.find(y)? "YES\n":"NO\n"); }
        else { int x; cin>>x; out += to_string(dsu.size(x)); out += '\n'; }
    }
    cout<<out;
    return 0;
}

import java.io.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0,l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    static class DSU {
        int[] fa, sz;
        DSU(int n){ fa=new int[n+1]; sz=new int[n+1]; for(int i=0;i<=n;i++){ fa[i]=i; sz[i]=1; } }
        int find(int x){ return fa[x]==x? x: (fa[x]=find(fa[x])); }
        void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return; if(sz[a]<sz[b]){int t=a;a=b;b=t;} fa[b]=a; sz[a]+=sz[b]; }
        int size(int x){ return sz[find(x)]; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        DSU dsu = new DSU(n);
        StringBuilder out = new StringBuilder();
        for(int i=0;i<m;i++){
            int op = fs.nextInt();
            if(op==1){ int x=fs.nextInt(), y=fs.nextInt(); dsu.unite(x,y); }
            else if(op==2){ int x=fs.nextInt(), y=fs.nextInt(); out.append(dsu.find(x)==dsu.find(y)?"YES\n":"NO\n"); }
            else { int x=fs.nextInt(); out.append(dsu.size(x)).append('\n'); }
        }
        System.out.print(out.toString());
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
fa = list(range(n+1))
sz = [1]*(n+1)

def find(x: int) -> int:
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x

out_lines = []
for _ in range(m):
    op = int(next(it))
    if op == 1:
        x = int(next(it)); y = int(next(it))
        rx, ry = find(x), find(y)
        if rx != ry:
            if sz[rx] < sz[ry]:
                rx, ry = ry, rx
            fa[ry] = rx
            sz[rx] += sz[ry]
    elif op == 2:
        x = int(next(it)); y = int(next(it))
        out_lines.append('YES' if find(x) == find(y) else 'NO')
    else:
        x = int(next(it))
        out_lines.append(str(sz[find(x)]))

sys.stdout.write('\n'.join(out_lines))