NC235745 拆路 (并查集)

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

const int N = 1e5 + 10;
int fa[N],cnt[N],st[N],en[N],a[N],b[N],ans[N];
set<pair<int,int>>t;

int find(int i){
    if(fa[i] == i) return i;
    return fa[i] = find(fa[i]);
}

void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if(cnt[fx] > cnt[fy]) fa[fy] = fx;
    else fa[fx] = fy;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i] = i;
        cin>>cnt[i];
    }
    for(int i=1;i<=m;i++) cin>>st[i]>>en[i];
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        char op;
        cin>>op;
        if(op == 'Q'){
            cin>>a[i];
        }
        else{
            cin>>a[i]>>b[i];
            t.insert({a[i],b[i]});
            t.insert({b[i],a[i]});
        }
    }
    for(int i=1;i<=m;i++){
        if(t.find({st[i],en[i]})==t.end())
            merge(st[i],en[i]);
    }
    for(int i=q;i>=1;i--){
        if(b[i]) merge(a[i],b[i]);
        else ans[i] = cnt[find(a[i])];
    }
    for(int i=1;i<=q;i++)
        if(ans[i]) cout<<ans[i]<<'\n';
    return 0;
}