合并集合

模板题，只需要了解find函数即可.

int find(int x){
    if(p[x] != x) p[x] = find(x);//一直递归知道找到祖先节点
    return p[x];
}

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int p[100005],n,m;
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) p[i] = i;
    while(m --){
        char t;
        int a,b;
        cin >> t >> a >> b;
        if(t == 'Q'){
            a = find(a),b = find(b);
            if(a == b){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else{
            a = find(a),b = find(b);
            p[a] = b;
        }
    }
    return 0;
}