题目链接
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
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
;
else
fx
<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
;
}
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
;
else
ans
[++cnt
]=-1;
}
}
for(int i
=cnt
;i
>=1;i
--)
cout
<<ans
[i
]<<endl
;;
}
return 0;
}
