解题思路 本题是并查集的经典模板题。 优化 路径压缩：查询根节点时直接将节点指向根

按集合大小合并：将小集合合并到大集合上，避免树退化成链表，保证合并效率；（随便orz）

数组维护：用数组记录每个节点的父节点、每个集合的元素数量。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n,m;
// a:父节点数组  h:集合大小数组
int a[100100],h[100100];
// 查找根节点 + 路径压缩
int find(int x){
    if(a[x]==x)return x;
    return a[x]=find(a[x]); 
}
int merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)return 0; // 同一集合，无需合并
    // 按大小合并：小挂到大
    if(h[fx]>h[fy])swap(fx,fy);
    a[fx]=fy;
    h[fy]+=h[fx]; // 更新大小
    return 1;
}
signed main(){
    cin>>n>>m;
    // 初始化：每个元素的父节点是自己，集合大小为1
    for(int i=1;i<=n;i++){
        a[i]=i;
        h[i]=1;
    }
    while(m--){
        char op;
        cin>>op;
        if(op=='C'){
            // 合并操作
            int x,y;
            cin>>x>>y;
            if(x==y)continue;
            merge(x,y);
        }
        else if(op=='Q'){
            int type;
            cin>>type;
            if(type==1){
                // 查询x和y是否连通
                int x,y;
                cin>>x>>y;
                cout<<(find(x)==find(y)?"Yes\n":"No\n");
            }
            else{
                // 查询x所在集合的大小
                int x;
                cin>>x;
                cout<<h[find(x)]<<'\n';
            }
        }
    }
}

板子题，没啥好说的

import java.io.*;

public class Main{   //并查集
    static int n,m;
    static StreamTokenizer st;
    static PrintWriter pw;
    static int[]father,size;

    static int Find(int n)  //寻找根节点
    {
        if(n==father[n]) return n;
        father[n]=Find(father[n]);
        return father[n];
    }
  
    static boolean Query(int a,int b)
    {
        a=Find(a);
        b=Find(b);
        return a==b;
    }

    static void Hebing(int a,int b)
    {
        a=Find(a);
        b=Find(b);
        if(a==b) return;
        if (size[a] < size[b]) {  //小的合并大的里
            father[a]=b;
            size[b]+=size[a];
        } else {
            father[b]=a;
            size[a]+=size[b];
        }
    }
    public static void main(String[] args) throws IOException {
        st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        pw=new PrintWriter(System.out);
        st.nextToken();
        n= (int) st.nval;
        st.nextToken();
        m= (int) st.nval;
        father=new int[n+1];
        size=new int[n+1];
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
            size[i]=1;
        }
        for(int i=1;i<=m;i++)
        {
            st.nextToken();
            String ope=st.sval;
            switch (ope)
            {
                case "Q1":
                {
                    st.nextToken();
                    int a= (int) st.nval;
                    st.nextToken();
                    int b= (int) st.nval;
System.out.println(Query(a,b)?"Yes":"No");
                    break;
                }
                case "Q2":
                {
                    st.nextToken();
                    int a= (int) st.nval;
        System.out.println(size[Find(a)]);
                    break;
                }
                case "C":  //连接
                {
                    st.nextToken();
                    int a= (int) st.nval;
                    st.nextToken();
                    int b= (int) st.nval;
                    Hebing(a,b);
                    break;
                }
            }
        }
    }
}

JAVA AC代码(并查集):

import java.util.*;
import java.util.StringTokenizer;
import java.io.*;

public class Main {
    static int fa[],size[];
    public static void main(String[] args) {
        int n=in.nextInt(),m=in.nextInt();
        fa=new int[n+1];//父节点数组
        size=new int[n+1];//记录每个节点包含的节点个数,每颗树的调用用size[find(i)]
        for(int i=1;i<=n;i++){
            fa[i]=i;//每个节点的父节点首先标记为自己
            size[i]=1;//每个节点都是一棵树，节点个数为1
        }
        while(m-->0) {
            String op=in.next();
            if(op.equals("C")) {
                int u=in.nextInt(),v=in.nextInt();
                int fu=find(u),fv=find(v);//不在同一棵树上
                if(fu!=fv) {
                    fa[fu]=fv;//将u的根节点的父节点标记为v的根节点
                    size[fv]+=size[fu];//fv为整颗树的根，所以用size[fv]加
                }
            }else if(op.equals("Q1")) {
                int u=in.nextInt(),v=in.nextInt();
                int fu=find(u),fv=find(v);
                out.println(fu==fv?"Yes":"No");//根节点是否相同
            }else {
                int u=in.nextInt();
                out.println(size[find(u)]);
            }
        }
        out.close();
        out.close();
    }
    
    public static int find(int x){
        if(fa[x]!=x) fa[x]=find(fa[x]);
        return fa[x];
    }

    static FastReader in=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            String str="";
            while(st==null||!st.hasMoreElements()) {
                try {
                    str=br.readLine();
                }catch(IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}