题解：做到一种并查集的新题型，在状态压缩的时候传递祖先的信息，每个根结点都是最多移动一次的，所以记录移动次数把自己的加上父亲结点的就是移动总数了。
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48 |
#include <cstdio> #include <cstring> const
int MAXN=10010; int n,q,count[MAXN],f[MAXN],move[MAXN]; int sf(int
x){ if(f[x]==x) return
x; int
t=f[x]; f[x]=sf(f[x]); move[x]+=move[t]; return
f[x]; } void
Union(int
x,int y){ x=sf(x); y=sf(y); if(x!=y){ f[x]=y; count[y]+=count[x]; move[x]=1; } } int
main(){ int
T; scanf("%d",&T); int
cas=1; while(T--){ scanf("%d%d",&n,&q); for(int
i=1;i<=n;i++)count[i]=1; for(int
i=1;i<=n;i++)f[i]=i; memset(move, 0, sizeof(move)); char
str[10]; printf("Case %d:\n",cas++); for(int
i=1;i<=q;i++){ scanf("%s",str); if(str[0]==‘T‘){ int
x,y; scanf("%d%d",&x,&y); Union(x,y); } else{ int
x; scanf("%d",&x); int
fx=sf(x); printf("%d %d %d\n",fx,count[fx],move[x]); } } } return
0; } |
原文：http://www.cnblogs.com/forever97/p/3550560.html