11118: 【原1118】Travel

题目

题目描述

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

Description

一家城际旅游公司在N个城市之间安排旅行。初始时，每个城市分别有一个旅行团；为了方便行程安排，当一个城市的旅行团从一个城市旅行到另一个城市时，这两个旅游团就会合并到一起。

Input Format

第一行，N, M：表示有N个城市，以及接下来有M行。(2 < N, M<= 10000)

第2至M+1行：(1 <= a, b <= N)

每行是一个行程安排：T a b 表示a号旅行团所在城市的旅行团，一起去b号旅行团所在城市旅行。

或者一个查询：Q a 表示询问当前状态下，当前a号旅行团所在城市X，以及X所在城市一共有多少个原始旅行团C，以及a号旅行团当前去过多少个城市T。（不包含初始时所在的城市，一个城市可计算多次）

Output Format

对于每一个查询Q a，输出一行三个数X C T

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;
}