# 11118: 【原1118】Travel

### 题目描述

author: Zhiming Zhou 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1118

## Sample Input 1

``````3 3
T 1 2
T 3 2
Q 2
``````

## Sample Output 1

``````2 3 0
``````

## Sample Input 2

``````3 4
T 1 2
Q 1
T 1 3
Q 1
``````

## Sample Output 2

``````2 2 1
3 3 2
``````

## FineArtz's solution

``````/* Travel */
#include <iostream>
using namespace std;

int n, m;
int parent[10005], now[10005], nowat[10005], sum[10005], trl[10005], ex[10005];

int find(int x){
if (parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}

void merge(int x, int y){
int p = find(x), q = find(y);
sum[q] += sum[p];
//    if (sum[p] > sum[q]){
//        int t = p;
//        p = q;
//        q = t;
//    }
for (int i = 1; i <= n; ++i){
int t = find(i);
if (t == p || t == q)
trl[i] += ex[t];
}
ex[p] = ex[q] = 0;
parent[p] = q;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
parent[i] = i;
now[i] = i;
nowat[i] = i;
sum[i] = 1;
trl[i] = 0;
ex[i] = 0;
}
while (m--){
char ch;
int x, y, p, q, a, b;
cin >> ch;
switch(ch){
case 'T':
cin >> x >> y;
p = find(x); //the set contains x
q = find(y); //the set contains y
if (p != q){
a = nowat[p]; //where p is
b = nowat[q]; //where q is
now[a] = -1;
nowat[p] = b;
++ex[p];
merge(y, x);
}
break;
case 'Q':
cin >> x;
p = find(x);
cout << nowat[p] << ' ' << sum[p] << ' ' << trl[x] + ex[p] << '\n';
break;
}
}
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 10010
using namespace std;

int n, m;
int father[MAX_N], num_of_cities[MAX_N];
vector<int> son[MAX_N];

int find(int x) {
if (father[x] == x) return x;
father[x] = find(father[x]);
return father[x];
}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;
for (int i = 1; i <= n; ++i) {
father[i] = i;
son[i].push_back(i);
}

while (m--) {

char op; cin >> op;
if (op == 'T') {
int group_id, des;
cin >> group_id >> des;
int cur_place = find(group_id);
des = find(des);
if (cur_place == des)
continue;
for (int i = 0; i < son[cur_place].size(); ++i)
++num_of_cities[son[cur_place][i]];
son[des].insert(son[des].end(), son[cur_place].begin(), son[cur_place].end());
son[cur_place].clear();
father[find(cur_place)] = des;
}
else {
int group_id;
cin >> group_id;
int cur_place = find(group_id);
printf("%d %d %d\n", cur_place, son[cur_place].size(), num_of_cities[group_id]);
}
}

return 0;
}
``````