题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2049
LCT裸题
啊啊啊看到能用并查集果断放弃LCT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<bits/stdc++.h> #define MAXN 10010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m; char c[10]; int fa[MAXN]; inline void sroot(int x){for(int i=0,f=fa[x]; x; f=fa[x])fa[x]=i,i=x,x=f;} int main(){ n=rd(),m=rd(); while(m--){ scanf("%s",c); int x=rd(),y=rd(); sroot(x); if(c[0]=='C')fa[x]=y; else if(c[0]=='D')fa[y]=0; else{ while(y && x!=y)y=fa[y]; puts(x==y?"Yes":"No"); } } return 0; } |