https://cn.vjudge.net/problem/ZOJ-3261
题意
银河系各大星球之间有不同的能量值， 并且他们之间互相有通道连接起来，可以用来传递信息，这样一旦有星球被怪兽攻击，便可通过通道找到能量值最大的星球来帮忙。但是有一些通道被怪兽破坏了。
现在先给出原来的所有通道， 然后进行询问，询问有两种方式：
destroy a b： 连接a，b的通道被怪兽破坏了
query a: 询问a能否通过通道找到救兵，只能找能量值比自己大的救兵。
分析
逆向思维，先离线存储所有的输入操作，然后把被完全破坏之后的通道连接起来，然后再从最后一个询问往前面推，当有destroy a b时就把a,b再Union起来。
这里使用哈希思想来判断一条边是否被破坏了，注意格式。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = + ;
const int maxm = + ;
const int mod = ;
int fa[maxn];
int n,m;
struct ND{
char op[];
int a,b;
};
vector<ND> ask;
int HASH = maxn;
vector<pair<int,int> >edge;
int w[maxn];
int ans[];
map<int,bool> ma;
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
if(w[fx]>w[fy]){
fa[fy]=fx;
}else if(w[fx]<w[fy]){
fa[fx]=fy;
}else{
if(fx>fy){
fa[fx]=fy;
}else{
fa[fy]=fx;
}
}
}
} int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
bool flag=false;
while(~scanf("%d",&n)){
for(int i=;i<n;i++) scanf("%d",&w[i]);
for(int i=;i<=n;i++) fa[i]=i;
edge.clear();
ask.clear();
ma.clear();
scanf("%d",&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
edge.push_back(make_pair(x,y));
}
int q;
scanf("%d",&q);
while(q--){
ND tmp;
scanf("%s",tmp.op);
if(tmp.op[]=='q'){
scanf("%d",&tmp.a);
}else{
scanf("%d%d",&tmp.a,&tmp.b);
if(tmp.a>tmp.b) swap(tmp.a,tmp.b);
ma[tmp.a*HASH+tmp.b]=true;
}
ask.push_back(tmp);
}
q=edge.size();
for(int i=;i<q;i++){
if(ma[edge[i].first*HASH+edge[i].second]) continue;
Union(edge[i].first,edge[i].second);
}
// for(int i=0;i<n;i++) printf("%d ",fa[i]);puts("");
q=ask.size();
int cnt=;
for(int i=q-;i>=;i--){
if(ask[i].op[]=='q'){
int f=find(ask[i].a);
if(w[f]>w[ask[i].a]) ans[cnt++]=f;
else ans[cnt++]=-;
}else{
// cout<<ask[i].a<<' '<<ask[i].b<<endl;
Union(ask[i].a,ask[i].b);
// for(int i=0;i<n;i++) printf("%d ",fa[i]);puts("");
}
}
if(flag) puts("");
flag=true;
for(int i=cnt-;i>=;i--) printf("%d\n",ans[i]); }
return ;
}