总体来说，这个题给的时间比较长，样例也是比较弱的，别的方法也能做出来。
我第一次使用的是不合并路径的并查集，几乎是一种暴力，花了600多MS，感觉还是不太好的，发现AC的人很多都在300MS之内的过得。
看到他们的做法后，我知道了这个题比较好的做法。
逆向思维的并查集，因为这里只有去边操作，完全可以离线计算，把删边当成加边，然后逆序输出答案即可。
但是，这个却有一个坑，很坑，只有第一次删除的时候，我们才对他进行操作，加边的时候也只能在第一次删除的时候加。当时因为这里，十分困惑……
这是我无路径压缩的并查集的做法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define N 20005
int n,fa[N];
int Find(int x){
while(x != fa[x]){
x = fa[x];
}
return x;
}
int main() {
// freopen("E.in.cpp","r",stdin);
int T,k,ca=,p,a,b;
scanf("%d",&T);
char op[];
while(T--) {
scanf("%d%d",&n,&k);
for(int i = ; i <= n; i++) {
fa[i] = i;
}
for(int i = ; i <= n; i++) {
scanf("%d",&p);
if(p == ) fa[i] = i;
else {
fa[i] = p;
}
}
printf("Case #%d:\n",++ca);
while(k--) {
scanf("%s",op);
if(op[] == 'C') {
scanf("%d",&b);
if(fa[b] == b) continue;
fa[b] = b;
} else {
scanf("%d%d",&a,&b);
if(Find(a) != Find(b)) {
printf("NO\n");
} else printf("YES\n");
}
}
}
return ;
}
这是逆序离线并查集的做法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N = 2e4+;
int n,fa[N],pa[N],vis[N];
string ans[];
struct Query {
int a,b,kind;
void Set(int A,int B,int k) {
a = A;
b = B;
kind = k;
}
} q[];
int Find(int x) {
return fa[x]==x? x :fa[x]=Find(fa[x]);
}
void Union(int a,int b) {
fa[Find(b)] = Find(a);
}
int main() {
// freopen("E.in.cpp","r",stdin);
int T,k,ca=;
char op[];
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&k);
for(int i = ; i <= n; i++) {
scanf("%d",&pa[i]);
fa[i] = i;
vis[i] = ;
}
printf("Case #%d:\n",++ca);
int a,b;
for(int i = ; i < k; i++) {
scanf("%s",op);
if(op[] == 'C') {
scanf("%d",&a);
if(pa[a]!= && vis[a] != ) q[i].Set(a,,);
else q[i].Set(a,,-);
vis[a] = ;
} else {
scanf("%d%d",&a,&b);
q[i].Set(a,b,);
}
}
for(int i = ; i <= n; i++) {
if(vis[i]== || pa[i]==) continue;
Union(pa[i],i);
}
int cnt = ;
for(int i = k-; i >= ; i--) {
if(q[i].kind == -) continue;
else if(q[i].kind == ) {
if(Find(q[i].a) == Find(q[i].b)) ans[cnt++] = "YES";
else ans[cnt++] = "NO";
} else Union(pa[q[i].a],q[i].a);
}
for(int i = cnt-; i >= ; i--) {
cout<<ans[i]<<endl;
}
}
return ;
}