Connections in Galaxy War

题目

假设有编号从0开始的n个点，每个点都有一个非负权值p[i]。现在有没有重边的m条边和Q个操作。
对于操作有两种类型
destroy a b 表示摧毁a,b点之间的边
query a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最小的点。如果没有这样的点输出-1。

分析

此题如果在线处理询问的话，不得不面对一个问题，也就是并查集的拆分，拆分后维护就变得异常困难。所以我们可以将问题存储在栈里面，先处理好并查集的最终状态，然后反向处理，也就是相当于是合并，这是并查集所擅长的。
有一点需要注意：map<pii,bool> 存储了a，b两个连接的边是否完好，需要将a，b按a小，b大统一一下，保持前后一致性。

AC代码

#include <iostream>
#include <algorithm>
#include <map>
#include <stdio.h>
#include <string>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 1e4+10;

int N,M,Q;
int power[maxn],fa[maxn];
struct info{
    string op;
    int a,b;
}sk[5*maxn];int top;
map<pii,bool> mp;
int res[5*maxn],tail;
void init(){
    top = 0;tail = 0;
    mp.clear();
    for(int i = 0;i<N;i++) fa[i] = i;
}

int find(int x){
    if(x!=fa[x])
        fa[x] = find(fa[x]);
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){ //谁跟着谁看谁的能力大，其实是id小
        if(power[fx] > power[fy]) fa[fy] = fx;
        else if(power[fy] > power[fx]) fa[fx] = fy;
        else if(fx<fy) fa[fy] = fx;
        else fa[fx] = fy;
    }
}
int main(){
    int tag = 0;
    while(~scanf("%d",&N)){
        if(tag) puts("");
        tag = 1;
        init();
        for(int i = 0;i<N;i++) scanf("%d",&power[i]);
        cin>>M;
        int a,b;
        while(M--){
            scanf("%d %d",&a,&b);
            if(a>b) swap(a,b);
            mp[{a,b}] = true;
        }
        cin>>Q;
        string op;
        while (Q--){
            ++top;
            cin>>op;
            if(op=="query"){
                scanf("%d",&a);
                sk[top] = {op,a};
            }else{
                scanf("%d%d",&a,&b);
                if(a>b) swap(a,b);
                sk[top] = {op,a,b};
                mp[{a,b}] = false;//摧毁边
            }
        }
        for(const auto &m:mp){ //处理好并查集的最终状态
            if(m.second){
                int a = m.first.first,b = m.first.second;
                join(a,b);
            }
        }
        while(top){//反向处理
            if(sk[top].op == "query"){
                int t = find(sk[top].a);
                if(power[t] > power[sk[top].a]){
                    res[++tail] = t;
                }else{
                    res[++tail] = -1;
                }
            }else{
                join(sk[top].a,sk[top].b);
            }
            top--;
        }
        for(int i = tail;i;i--){ //反向输出
            printf("%d\n",res[i]);
        }
    }
    return 0;
}