参考链接：
http://www.cppblog.com/yuan1028/archive/2011/02/13/139990.html
http://blog.csdn.net/roney_win/article/details/9473225
题意：N个星球，编号从0到N-1。每个星球有一个战斗力power，且这N个星球之间建有一些通道，可以相互联系，在星球大战中，一些星球要向和自己联通的星球中power最强且大于自己的星球求救，且在星球大战中会有一些通道被损坏。
两种操作：破坏a和b之间的通道；a星球该向谁求救。
逆向并查集：
与并查集不同，给出一个图中原有的一些边，然后给出操作，操作不是向图中添加边，而是在已有的边上，将边删除。
对于该种情况，需要首先读入所有操作，把要求删除的边全部删除，再按照从后往前的顺序处理操作，这样删边操作转化为了添边的操作。
思路：我们先输入所有数据，即所谓的离线输入，将星球大战之后的状态作为初始状态，进行并查集的操作，遇到destroy时，就恢复a到b之间的通道，那么就很容易维护根节点的性质了，这题就变得很简单了。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm> using namespace std; const int maxn=;
int father[maxn];
long long power[maxn];
int n,m,q;
int ans[maxn*]; //存储最后要输出的答案 struct Edge{
int u,v,flag; //u、v表示边的端点，u<=v；flag=0表示改变被删除 //将u从小到大排序，若u相同时，按v从小到大排序
bool operator < (const Edge tmp)const {
if(u==tmp.u)
return v<tmp.v;
return u<tmp.u;
}
} edge[*maxn]; //先把所有的询问都存储下来
struct Query{
int k,a,b; //k=1表示操作是询问，k=2表示操作是删边
}query[maxn*]; struct Node {
int u; //u代表集合中具有最大能力值的点的编号
long p; //p代表集合中点的最大能力值
} node[maxn]; void init() {
for(int i=; i<n; i++) {
father[i]=i;
node[i].u=i;
node[i].p=power[i];
}
} int find_root(int x) {
if(father[x]!=x)
father[x]=find_root(father[x]);
return father[x];
} void Union(int x,int y) {
father[y]=x;
if(node[x].p<node[y].p){
node[x].p=node[y].p;
node[x].u=node[y].u;
}
else if(node[x].p==node[y].p && node[x].u>node[y].u){
node[x].u=node[y].u;
}
}
//二分查找边，a<=b
void findEdge(int a,int b){
int mid,mins=,maxs=m-;
while(mins<=maxs){
mid=(mins+maxs)>>;
if(a==edge[mid].u && b==edge[mid].v){
edge[mid].flag=;
return;
}
if(a<edge[mid].u){
maxs=mid-;
}
else if(a>edge[mid].u){
mins=mid+;
}
else{
if(b<edge[mid].v){
maxs=mid-;
}
else{
mins=mid+;
}
}
}
}
int main() {
int a,b,blank=;
char ch[];
while(scanf("%d",&n)!=EOF) {
memset(vis,,sizeof(vis));
if(blank==)
blank=;
else
puts("");
for(int i=;i<n;i++){
scanf("%I64d",&power[i]);
}
scanf("%d",&m);
for(int i=; i<m; i++) {
scanf("%d%d",&a,&b);
if(a<b) {
edge[i].u=a;
edge[i].v=b;
edge[i].flag=;
} else {
edge[i].u=b;
edge[i].v=a;
edge[i].flag=;
}
}
sort(edge,edge+m); //一开始忘记排序了
scanf("%d",&q);
for(int i=; i<q; i++) {
scanf("%s",ch);
if(ch[]=='q') {
scanf("%d",&a);
query[i].k=;
query[i].a=a;
query[i].b=-;
}
else{
scanf("%d%d",&a,&b);
int t;
if(a>b){
t=a;a=b;b=t;
}
findEdge(a,b);
query[i].k=;
query[i].a=a;
query[i].b=b;
}
}
int x,y;
init();
for(int i=;i<m;i++){
if(edge[i].flag==){
x=find_root(edge[i].u);
y=find_root(edge[i].v);
if(x!=y){
Union(x,y);
}
}
}
int u,v;
for(int i=q-;i>=;i--){
if(query[i].k==){
x=find_root(query[i].a);
if(node[x].p>power[query[i].a]){
ans[i]=node[x].u;
}
else{
ans[i]=-;
}
}
else{
u=query[i].a;
v=query[i].b;
x=find_root(u);
y=find_root(v);
if(x!=y){
Union(x,y);
}
ans[i]=-;
}
}
for(int i=;i<q;i++){
if(ans[i]==-)
continue;
printf("%d\n",ans[i]);
}
}
return ;
}