题目链接：
ZOJ 3261 Connections in Galaxy War
题意：
有n个点，每个点有权值，然后给出m条无向边。有两种操作：
query a.表示从a出发的能到达的所有点权值最大的点的编号（相同取编号最小，而且权值要比自己大）
如果存在这样的点输出最大权值，否则输出-1.
destory a,b 表示删除连接a,b的边
按照操作输入顺序，输出每次查询的结果。两个测试样例之间有空行。
分析：
主要是逆向处理。
把破坏的边从后往前依次先查询破坏后需要的查询然后修复这条边，直到查询结束。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=10010;
const int maxm=20010;
const int maxq=50010;int n,m,q,u,v,aa,bb,in,root;
int dtot,qtot;
int val[maxn],vis[maxm],ans[maxn],pre[maxn];
//ans[i]表示i能连接的最大能量,根节点为能量最大的点,且多个最大权值时序号最小
char s[10];struct Read{int a,b;
}read[maxm];struct Des{int a,b,num;
}des[maxq];//保存破坏操作struct Que{int a,num,ans;
}que[maxq];//保存查询操作void init(int n)
{dtot=qtot=0;for(int i=0;i<n;i++){pre[i]=i;ans[i]=val[i];}
}int find(int x)
{if(pre[x]==x) return x;int tmp=find(pre[x]);ans[x]=max(ans[x],ans[pre[x]]);return pre[x]=tmp;
}void mix(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){
//不在同一集合//if(ans[fx]>ans[fy]) //在fx集合可以找到更大能量if(val[fx]>val[fy]){
//其实val[fx]和ans[fx]以及val[fy]和ans[fy]都是一样的pre[fy]=fx;ans[fy]=ans[fx];}else if(val[fx]==val[fy]&&fx<fy){
//最大能量一样但是fx下标更小pre[fy]=fx;ans[fy]=ans[fx];}else{pre[fx]=fy;ans[fx]=ans[fy];}//不会存在fx和fy的最大能量一样，而且最大能量的下标也一样，因为这样就有交集了，就是一个集合了}
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endif // LOCALint first=1;while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&val[i]);init(n);memset(vis,0,sizeof(vis));scanf("%d",&m);for(int i=0;i<m;i++)scanf("%d%d",&read[i].a,&read[i].b);scanf("%d",&q);for(int i=0;i<q;i++){scanf("%s",s);if(s[0]=='q'){scanf("%d",&u);que[qtot].a=u;que[qtot].num=i;qtot++;}else{scanf("%d%d",&u,&v);des[dtot].a=u;des[dtot].b=v;des[dtot].num=i;dtot++;for(int j=0;j<m;j++)//查找读入的边，将要破坏的边标记{if(read[j].a==u&&read[j].b==v) vis[j]=1;if(read[j].a==v&&read[j].b==u) vis[j]=1;}}}for(int i=0;i<m;i++)//将永不被破坏的边合并{if(vis[i]) continue;aa=read[i].a;bb=read[i].b;mix(aa,bb);}in=qtot-1;//最后一条查询语句编号for(int i=dtot-1;i>=0;i--)//对每条破坏语句，从后往前开始修复{while(que[in].num>des[i].num)//所有在这条破坏的路和在上一条已经修好的路之间的查询语句{//printf("que[index].num=%d\n",que[index].num);aa=que[in].a;if(val[find(aa)]==val[aa]) que[in].ans=-1;//如果能连接的最大能量和自身能量一样//两种情况：①本身即是根节点②根节点能量和自身一样但序号小else que[in].ans=find(aa);//printf("que[index].ans=%d\n",que[index].ans);in--;}aa=des[i].a;bb=des[i].b;mix(aa,bb);//修复}//在第一条破坏路径之前的查询语句，也就是所有路都不破坏时的查询while(in>-1){aa=que[in].a;if(val[find(aa)]==val[aa]) que[in].ans=-1;else que[in].ans=find(aa);in--;}if(first) first=0;else printf("\n");for(int i=0;i<qtot;i++)printf("%d\n",que[i].ans);}return 0;
}