题意 给许多个 x,y,k, 若 k=1,x==y, 否则 x!=y, 如果矛盾, 输出 NO, 否则 YES
对于 k=1, 并查集简单操作一下, k=0, 如果 find(x)==find(y), 打个标记, 输出 NO;
有一个需要注意的地方是, 对于询问我们要进行 sort, 使 k=1 的情况先执行, 这样可以保证最后判断的答案正确.
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int re(){
- char c=getchar();int all=0,pd=1;
- for(;c>'9'||c<'0';c=getchar()) if(c=='-') pd=-1;
- while(c>='0'&&c<='9') all=all*10+c-'0',c=getchar();return all*pd;
- }const int N=3e4+5;int f[N],front[N],num[N];
- int find(int x){
- if(x==f[x]) return x;
- int fa=find(f[x]);front[x]+=front[f[x]];return f[x]=fa;
- }int abs(int x){return x>0?x:-x;}
- int main(){
- int n=re();for(int i=1;i<=30000;i++) num[i]=1,f[i]=i;
- for(int i=1;i<=n;i++){
- char c;cin>>c;
- int x=re(),y=re();
- int r1=find(x),r2=find(y);
- if(c=='M'){
- front[r1]+=num[r2];
- f[r1]=r2;num[r2]+=num[r1];
- num[r1]=0;
- }else if(r1!=r2) printf("-1\n");
- else printf("%d\n",abs(front[x]-front[y])-1);
- }
- }
来源: http://www.bubuko.com/infodetail-2738087.html