ZOJ3261 Connections in Galaxy War(逆向并查集+删边)

题目链接

Sample Input

2
10 20
1
0 1
5
query 0
query 1
destroy 0 1
query 0
query 1

Sample Output

1
-1
-1
-1

思路

题意在此就不赘述了，相较寻常并查集增添了删边的操作。怎样才可以在并查集中实现删边的操作呢？我们可以选用逆向的方法。首先我们将所有应删边去除后的其余边进行连接，然后从后往前对操作进行实现。当需要查询时，就查询当前情况是否符合题目要求，对结果进行记录；当需要删边时将此边恢复，则可以回到上一次查询时的状态，记录所有答案后再逆序输出即可。

代码

#include<map>
#include<stack>
#include<queue>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define pb push_back
//#include<bits/stdc++.h>
using namespace std;
const int P=1e9+5;
const int mod=1e9+7;
const int maxn=5e4+5;
typedef long long ll;
const int inf=0x3f3f3f3f;
char s[50];
bool erase[maxn];
int m,n,q,u,v,ca,cnt,a[maxn],ans[maxn],pre[maxn];
struct node
{
    int u,v;bool vis;
}edge[maxn],node[maxn];
int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}
void add(int x,int y)
{
    int fx=find(x);int fy=find(y);if(fx!=fy){
    if(a[fx]!=a[fy])a[fx]>a[fy]?pre[fy]=fx:pre[fx]=fy;//按照权值大小elsefx<fy?pre[fy]=fx:pre[fx]=fy;//按照编号大小}
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n){
    cnt=0;map<pair<int,int>,int>mp;memset(erase,false,sizeof erase);if(ca++)cout<<endl;for(int i=0;i<n;i++){
    pre[i]=i;cin>>a[i];}cin>>m;for(int i=0;i<m;i++){
    cin>>u>>v;if(u>v)swap(u,v);//按照大小关系进行处理，方便使用 edge[i].u=u;edge[i].v=v;mp[make_pair(u,v)]=i;//记录u,v对应编号}cin>>q;for(int i=0;i<q;i++){
    cin>>s;if(s[0]=='q'){
    cin>>u;node[i].u=u;node[i].vis=false;//未被摧毁}else{
    cin>>u>>v;if(u>v)swap(u,v);node[i].u=u;node[i].v=v;node[i].vis=true;//应被摧毁erase[mp[make_pair(u,v)]]=true;}}for(int i=0;i<m;i++)if(!erase[i])add(edge[i].u,edge[i].v);//先建残存边for(int i=q-1;i>=0;i--){
    if(node[i].vis)add(node[i].u,node[i].v);//重建被摧毁点else{
    int fu=find(node[i].u);if(a[fu]>a[node[i].u])ans[++cnt]=fu;//符合要求则记录答案elseans[++cnt]=-1;//不符合则记录-1}}for(int i=cnt;i>=1;i--)cout<<ans[i]<<endl;;}return 0;
}