标准并查集不带路径压缩不带按秩合并

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> fa;
int find(int x){
    // 最原始find：一路沿着父指针往上跳，直到跳到根
    // 根的特征：fa[x] == x
    while(fa[x]!=x) x=fa[x];
    return x;
}
void join(int a,int b){
    // 合并：把b所在集合的根，挂到a所在集合的根下面
    // 注意：这里不做按秩/按大小合并，也不做路径压缩
    int ra=find(a);
    int rb=find(b);
    if(ra==rb) return; // 已经在同一个家族
    fa[rb]=ra; // 合并两个家族
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>m;fa.assign(n+1,0);
    for(int i=1;i<=n;i++) fa[i]=i; // 初始化：每个人先各自成一个家族
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        join(a,b); // 已知亲戚关系：合并家族
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int c,d;cin>>c>>d;
        // 查询：如果两人的根相同，说明在同一个连通块（同一家族）
        if(find(c)==find(d)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

只路径压缩版本:

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> fa;
int find(int x){
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]); // 路径压缩：把x直接连到根节点
    return fa[x];
}
void join(int x,int y){
    int rx=find(x);
    int ry=find(y);
    if(rx==ry) return; // 已在同一家族，无需合并
    fa[ry]=rx; // 不考虑大小，直接把ry挂到rx下面
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>m;fa.assign(n+1,0);
    for(int i=1;i<=n;i++){
        fa[i]=i; // 初始化：每个人都是一个独立家族
    }
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        join(a,b); // 已知亲戚关系，合并两个家族
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int c,d;cin>>c>>d;
        // 如果两个人最终找到的根相同，说明在同一家族
        if(find(c)==find(d)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

路径压缩+按秩合并代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> fa,sz;
int find(int x){
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]); // 路径压缩：把x直接挂到根，后续查询更快
    return fa[x];
}
void join(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx==ry) return;
    if(sz[rx]<sz[ry]) swap(rx,ry); // 小集合挂到大集合，树更矮
    fa[ry]=rx; // 合并两个家族
    sz[rx]+=sz[ry]; // 维护家族大小（本题可不需要，但合并优化常配套讲）
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    fa.assign(n+1,0);
    sz.assign(n+1,1);
    for(int i=1;i<=n;i++) fa[i]=i; // 初始化：每个人自成一个家族
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        join(a,b); // 已知亲戚关系：把两个人所在家族合并
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int c,d;
        cin>>c>>d;
        if(find(c)==find(d)) cout<<"Yes\n"; // 根相同：同一家族
        else cout<<"No\n"; // 根不同：不是亲戚
    }
    return 0;
}