还以为蛮高深的并查集呢，原来是个大水题，
n个城市n个球，m个查询，T表示把和x号求同样城市的球转移到y号球所在的城市，Q表示询问x号球在哪个城市，该城市有多少个球，x号球转移了几次
1 #include <iostream> 2 #include <cstdio> 3 #include <fstream> 4 #include <algorithm> 5 #include <cmath> 6 #include <deque> 7 #include <vector> 8 #include <queue> 9 #include <string> 10 #include <cstring> 11 #include <map> 12 #include <stack> 13 #include <set> 14 #define LL long long 15 #define eps 1e-8 16 #define INF 0x3f3f3f3f 17 #define OPEN_FILE 18 #define MAXN 10005 19 using namespace std; 20 int n, m; 21 int father[MAXN], step[MAXN], num[MAXN]; 22 //step[x]表示x移动了多少次，num[x]表示x号城市有几个球 23 int find(int x){ 24 if (father[x] == x) return x; 25 int y = father[x]; 26 father[x] = find(father[x]); 27 step[x] += step[y]; 28 return father[x]; 29 } 30 31 int main() 32 { 33 #ifdef OPEN_FILE 34 freopen("in.txt", "r", stdin); 35 //freopen("out.txt", "w", stdout); 36 #endif // OPEN_FILE 37 int T; 38 scanf("%d", &T); 39 for (int cas = 1; cas <= T; cas++){ 40 scanf("%d%d", &n, &m); 41 for (int i = 1; i <= n; i++){ 42 father[i] = i; 43 step[i] = 0; 44 num[i] = 1; 45 } 46 printf("Case %d: ", cas); 47 char ch; 48 int x, y; 49 for (int i = 1; i <= m; i++){ 50 scanf(" "); 51 scanf("%c", &ch); 52 if (ch == 'T'){ 53 scanf("%d%d", &x, &y); 54 //把与x相同城市的所有球移到y所在城市 55 int a = find(x), b = find(y); 56 num[b] += num[a]; 57 num[a] = 0; 58 step[a]++; 59 father[a] = b; 60 } 61 if (ch == 'Q'){ 62 scanf("%d", &x); 63 int a = find(x); 64 printf("%d %d %d ", a, num[a], step[x]); 65 } 66 } 67 } 68 }