智商拙计啊,这题看了解题报告都不是很懂,郁闷。。。。。
考虑了很长时间,才明白每个根结点最多只能移动一次,所以我们的目的就是把这一次push到各个子节点上就可以了,因为路径压缩的缘故,除了这次操作之外,所有的结点都挂在根节点上,完全水题一枚,被暴虐啊
code:
#include <cstdio> #include <cstring> using namespace std; const int MAXN = 10010; int n,m,fa[MAXN],cnt[MAXN],move[MAXN]; void init() { int i; for(i=1;i<=n;i++) { fa[i]=i; cnt[i]=1; move[i]=0; } } //一个根节点只能移动一次,所以只要把这个一次push下去就好了 int find(int x) { if(fa[x]!=x) { int t=fa[x]; fa[x]=find(fa[x]); move[x]+=move[t]; } return fa[x]; } void merge(int x,int y) { x=find(x); y=find(y); if(x!=y) { fa[x]=y; cnt[y]+=cnt[x]; move[x]=1; } } int main() { int cas,i,k,a,b; char str[2]; scanf("%d",&cas); for(k=1;k<=cas;k++) { scanf("%d%d",&n,&m); init(); printf("Case %d:\n",k); for(i=1;i<=m;i++) { scanf("%s",str); if(str[0]=='T') { scanf("%d%d",&a,&b); merge(a,b); }else{ scanf("%d",&a); b=find(a); printf("%d %d %d\n",b,cnt[b],move[a]); } } } return 0; }