P1551 亲戚 题解

Dijkstra_zyl · 2025-11-02 23:06:55 · 题解

P1551 亲戚 题解

一道很简单的并查集板子

上代码

#include <iostream>//并查集
using namespace std;
const int N = 5010;
int root[N],n,m,p;
void init(int i){ root[i] = i; }//先初始化 自己指向自己 
int find(int x){//找x的root 
    if(root[x] == x) return x;//x是root
    return root[x] = find(root[x]);//路径压缩
}
void merge(int x,int y){//合并两棵树 
    int rootx = find(x);
    int rooty = find(y);
    if(rootx != rooty) {
        if(rootx >= rooty) root[rootx] = rooty;
        else root[rooty] = rootx;
    }
}
int main(){
    cin >> n >> m >> p;
    for(int i = 1;i <= n;i++) init(i);
    for(int i = 1;i <= m;i++){
        int x,y; cin >> x >> y;
        merge(x,y);
    }
    while(p--){
        int x,y; cin >> x >> y;
        if(find(x) == find(y)) cout << "Yes\n";
        else cout << "No\n";
    }
}