ZOJ3261 Connections in Galaxy War 并查集

时间:2022-11-01 04:38:56

分析:对于这种删边操作,我们通常可以先读进来,然后转化离线进行倒着加边

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int>pii;
const int N=1e4+;
pii p[N<<];
int v[N],fa[N],n,m,q;
bool vis[N<<];
struct Ask{
int op,id,ans;
}ask[N*];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(v[x]>v[y]||(v[x]==v[y]&&x<y))fa[y]=x;
else fa[x]=y;
}
int main()
{
bool flag=;
while(~scanf("%d",&n)){
if(flag)flag=;
else printf("\n");
for(int i=;i<n;++i){
scanf("%d",&v[i]),fa[i]=i;
}
memset(vis,,sizeof(vis));
scanf("%d",&m);
for(int i=;i<=m;++i){
scanf("%d%d",&p[i].first,&p[i].second);
if(p[i].first>p[i].second)swap(p[i].first,p[i].second);
}
sort(p+,p++m);
scanf("%d",&q);
for(int i=;i<=q;++i){
char s[];
int u,v;
scanf("%s%d",s,&u);
if(s[]=='q'){
ask[i].op=;
ask[i].id=u;
}
else{
ask[i].op=;
scanf("%d",&v);
if(u>v)swap(u,v);
ask[i].id=lower_bound(p+,p++m,make_pair(u,v))-p;
vis[ask[i].id]=;
}
}
for(int i=;i<=m;++i){
if(vis[i])continue;
Union(p[i].first,p[i].second);
}
for(int i=q;i>;--i){
if(ask[i].op==){
ask[i].ans=find(ask[i].id);
if(v[ask[i].ans]==v[ask[i].id])ask[i].ans=-;
}
else Union(p[ask[i].id].first,p[ask[i].id].second);
}
for(int i=;i<=q;++i)if(ask[i].op==)printf("%d\n",ask[i].ans);
}
return ;
}