题意：有n个龙珠，第i个在第i个城市，有两种操作： 1、T x y , 把第x个龙珠所在城市的所有龙珠转移到第y个龙珠的所在城市。（题目保证所在城市不同） 2、Q x ，输出第x个龙珠所在城市，该城市的龙珠数量和该龙珠转移的次数。
思路： 一看就是个并查集的题目，城市的龙珠的所在城市以及城市的龙珠数量很好求，龙珠的转移次数要处理一下。龙珠的转移次数等于该龙珠的转移次数+他的所有父亲的转移次数。
用递归即可解决，好好理解。
#include <iostream> #include <cstdio> #include <map> #include <set> #include <cmath> #include <queue> #include <stack> #include <unordered_set> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define ll long long #define inf 0x3f3f3f3f #define pb push_back #define T int T;scanf("%d",&T);while(T--) const ll mod=1e9+7; int f[100005]; //父亲 int sum[100005]; //城市的龙珠数量 int t[100005]; //转移次数 int find(int x){ if(x==f[x]) return x; int p = find(f[x]); //递归。。。。（关键操作） t[x] += t[f[x]]; //转移次数=该龙珠转移次数+父亲龙珠转移次数 f[x] = p; // 路径压缩 return f[x]; } int main(){ int tt = 1; T{ int n,m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i ++){ f[i] = i; sum[i] = 1; t[i] = 0; } printf("Case %d:\n", tt++); while(m--){ char c; getchar(); scanf("%c", &c); int x,y; if(c=='T'){ scanf("%d %d", &x, &y); int xx = find(x); int yy = find(y); sum[yy] += sum[xx]; //转移龙珠 f[xx] = yy; t[xx] = 1; }else{ scanf("%d", &x); y = find(x); printf("%d %d %d\n", y, sum[y], t[x]); } } } return 0; } /* 4 4 T 1 2 T 2 3 T 3 4 Q 1 4 4 T 1 2 T 2 3 T 2 4 Q 3 */