백준 #3780 네트워크 연결


BOJ #3780 - 네트워크 연결

https://www.acmicpc.net/problem/3780

# 문제 분류

Disjoint Set

풀이 접근 방법


센터만 바뀐다는 것을 알아야 해결할 수 있는 것 같은데.. find 연산을 요리조리 바꾸면 된다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, T, b, c, p[20010], dist[20010], up[20010];
char tmp, a;

int find(int n) {
    if (p[n] == n) {
        dist[n] = 0;
        return n;
    }

    // 기존의 루트 보존
    int tmp = find(p[n]);
    dist[n] += dist[p[n]];
    p[n] = tmp;

    return p[n];
}

void merge(int a, int b) {
    dist[a] = abs(a - b) % 1000;
    p[a] = b;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;

    fup(_, 1, T, 1) {
        cin >> N;

        fup(j, 1, N, 1) {
            p[j] = j;
        }

        while (true) {
            cin >> a;
            if (a == 'O')
                break;

            if (a == 'E') {
                cin >> b;
                find(b);
                cout << dist[b] << endl;
            }

            if (a == 'I') {
                cin >> b >> c;
                merge(b, c);
            }
        }
    }
}