镜像点思路
具体见这篇博客
i的信息存在i'里在2操作时就不会有影响
#include<bits/stdc++.h> #define N 200003 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int fa[N],num[N],sum[N]; void init(int n) { for(int i=1;i<=n;++i) { fa[i]=i+n;fa[i+n]=i+n; sum[i+n]=i;num[i+n]=1; } } int get(int x) { if(fa[x]==x)return x; return fa[x]=get(fa[x]); } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { init(n); for(int i=1;i<=m;++i) { int op=read(); if(op==1) { int p=read(),q=read(); int f1=get(p),f2=get(q); if(f1==f2)continue; fa[f1]=f2; sum[f2]+=sum[f1]; num[f2]+=num[f1]; } else if(op==2) { int p=read(),q=read(); int f1=get(p),f2=get(q); if(f1==f2)continue; fa[p]=f2; sum[f1]-=p;num[f1]--; sum[f2]+=p;num[f2]++; } else { int p=read(); int f=get(p); printf("%d %d ",num[f],sum[f]); } } } }