ZOJ3261(Connections in Galaxy Wa

链接：https://vjudge.net/problem/ZOJ-3261
思路：有几天没做并查集了，这个题我们先按权值合并，小的向大的合并，如果权值相等我们考虑编号，我们将所有命令先读入，然后在从末态开始输出询问，destroy就变成了建边，每次合并时同上合并方式，询问时检查一下当前点的权值和父节点权值是否相等，如果相等则无解，否则记录答案（一定要先getroot一下啊不然上次更新的并没有传递上去，这个地方已经错了很多次了长点记性啊拜托！！！！）
代码：

#pragma GCC diagnostic error "-std=c++11"  
#include<bits/stdc++.h>
using namespace std;

const int maxn = 60010;

int n,m,q;
set<pair<int,int> > edge;

struct order{
    int o,u,v;
}ss[maxn];

int maxv[maxn];
int par[maxn];
int ans[maxn];
char ch[100];

int getroot(int a){
    if(par[a]==a)return a;
    return par[a] = getroot(par[a]);
}

void merge(int u,int v){//先按权值合并，权值相同按编号合并
    int p1 = getroot(u);
    int p2 = getroot(v);
    if(p1==p2)return ;
    if(maxv[p1]>maxv[p2]){
        par[p2] = p1;
    }
    else if(maxv[p1]<maxv[p2]){
        par[p1] = p2;
    }
    else{
    if(p1<p2){
        par[p2] = p1;
    }
    else if(p1>p2){
        par[p1] = p2;
    }
}
}

int main(){
    int kase = 0;
    while(~scanf("%d",&n)){
        if(kase++)printf("\n");
        edge.clear();
        for(int i=0;i<=n;i++)par[i] = i;
        for(int i=0;i<n;i++)scanf("%d",&maxv[i]);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            if(u>v)swap(u,v);
            edge.insert(make_pair(u,v));
        }
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            int a,b;
            scanf("%s%d",ch,&a);
            if(ch[0]=='q'){
                ss[i].o = 0;
                ss[i].u = a;
            }
            else if(ch[0]=='d'){
                scanf("%d",&b);
                if(a>b)swap(a,b);
                ss[i].o = 1;
                ss[i].u = a;
                ss[i].v = b;
                edge.erase(make_pair(a,b));
            }
        }
        for(auto &it:edge){//将现村的边进行更新
            int u = it.first;
            int v = it.second;
            merge(u,v);
        }
        for(int i=q-1;i>=0;i--){
            if(!ss[i].o){
                getroot(ss[i].u);//！！！！！一定要记得先路径压缩一下更新最新的父节点！！！！！
                if(maxv[ss[i].u]!=maxv[par[ss[i].u]])
                ans[i] = par[ss[i].u];
                else ans[i] = -1;
            }
            else{
                ans[i] = -2;
                int u = ss[i].u;
                int v = ss[i].v;
               merge(u,v);
        }
        }
        for(int i=0;i<q;i++){
            if(ans[i]!=-2)
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}