UVa OJ 11987 Corporative Network

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075

해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다..

\(5\leq{N}\leq{2\cdot{10^4}}\)

\(0\leq{M}\leq{2\cdot{10^5}}\)

N은 회사의 수, M은 쿼리의 수

N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에

센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의  덩어리의 센터에서 나머지 덩어리의 아무 회사로

도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 1000 이다.

이 때 M개의 쿼리가 들어오는데 두가지의 operation이 있다.

E a : a번 회사 부터 이 회사가 속한 덩어리의 센터까지의 거리 출력

I a b : A 덩어리의 센터인 a와 B덩어리의 임의의 회사인 b 사이에 도로를 놓아 병합을 하고 센터는 B덩어리의 센터로 한다.

우선 병합을 하여 센터를 하나만 남긴다는 것을 보았을 때, 센터를 루트 노드로 갖는 상호배타적 집합의 트리에서

A 집합의 루트 노드인 a를 B 집합의 임의의 노드 b의 자식으로서 연결하여 병합하는 것을 떠올릴 수가 있다.

일반적으로 유니온파인드에서 병합을 할 때에는

a가 속한 집합의 루트노드와 b가 속한 집합의 루트노드간의 직접적인 연결관계를

주지만 이 문제에서는 정확히 주어진 두 노드간의 연결이 필요하다는 점에서 차이가 있다.

그러면 naive 하게 생각하여 각각의 노드에 대해 부모노드와 그 부모노드사이의 거리를 저장하면, 즉

parent[u] : u 노드의 부모 노드

dist[u] : u 노드와 u 노드의 부모노드 간의 거리

와 같은 두개의 일차원 배열을 가지고 'I' operation 에서는 말 그대로 그냥 parent[a] = b, dist[a] = abs(a-b)

해주고 'E' operation 에서는 부모를 찾아 거슬러 올라가면 문제를 해결할 수 있을 것이다.

그런데 이 문제에서는 집합의 루트를 탐색하는 동작의 시간복잡도를 줄이기 위해 함부로 부모를 루트로 바꾸어

압축시키는 행위를 하면 안된다. 왜냐하면 거리라는 변수도 존재하기 때문에 부모가 바뀌면

거리도 바뀌어야 하기 때문이다. 그래서 I a b 라는 쿼리가 들어오면 일반적으로 유니온 파인드에서 

find 시간을 줄여주기위해 사용하는 테크닉들을 사용하지 못하며 그대로 a와 b를 이어주는 수 밖에 없다. 그러면

M개의 쿼리중 최대 N번의 병합을 하며, 부모를 거슬러 올라가는 데에는 최대 O(N) 의 시간이 걸리기 때문에

O(NM) 의 시간이 걸린다. 그런데 병합의 최대 N번하며 병합을 할 때에는 그냥 parent[a] = b, dist[a] = abs(a-b) 를

하기 때문에 O(1) 이 걸리며, 병합을 한 다음에 그 다음 번 병합을 하기 전 까지는 일단 N개에 대해 답을 구해놓으면

새로 더 구할 필요가 없기 때문에 실제로는 O(N^2) 이 걸릴 것이다. 하지만 N은 최대 2만이기 때문에 시간안에

돌기는 힘들다. 그렇다면 find 를 하는 시간을 단축시킬 만한 방법을 떠올려보자.

아까 전에 find 를 하면서 부모를 루트로 바로 이어주는 압축 행위가 안된다고 하면서 그 이유로

여기서는 두 집합을 병합할 때 주어진 특정 노드간에 간선을 통해 병합이 되며

이것이 각 노드에서 루트까지의 거리를 구하는 데에 필요하기 때문에

노드간의 연결관계를 바꾸면 dist도 바꿔줘야 하기 때문이라고 했다.

그러면 parent와 같이 dist도 빠르게 바꿀 수만 있으면 된다는 뜻이다.

사실 압축을 할 때에 연결관계가 바뀌는 부분은 시작노드에서 루트노드까지 거슬러 올라가는 경로 상에 존재하는

노드들 뿐이다. 그렇기 때문에 이 노드들만 부모를 변경할 때에 거리도 압축시켜(거슬러 가는 동안의 거리의 합으로)

주면 된다.  그럼 어떻게 할까?

거슬러 올라가는 함수를 구현할 때에 인자로 부모만 주는게 아니라 지금까지 거슬러온 거리의 합을

같이 올려준다.  그리고 루트노드를 찾았다면 루트노드만 리턴하는 것이아니라 지금까지 거슬러온 거리의 합을

같이 리턴해준다. 그러면 리턴이 됐을 때에 출발노드부터 루트노드까지의 거리 S를 알 수가 있고, 또

출발노드부터 현재노드까지의 거리 D를 알 수가 있기 때문에

S - D 를 통해 현재 노드부터 루트노드 까지의 거리를 알 수가 있다!

그럼 그냥 이걸로 dist[u] 를 갱신해 주고 parent[u] 는 루트노드로 갱신해주면 압축이 가능하게되는것이다!

압축이 됐기 때문에 find 를 하는데에 걸리는 시간복잡도는 일단 한번 압축을 한 노드에 대해서는 상수시간이

걸리기 때문에 엄청나게 빠를 것이다. 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int parent[20003];
int dist[20003];
int T,N;
 
pair<int, int> find(int p, int acc){
    if(p==parent[p]) return {p, acc};
    auto ret = find(parent[p], acc + dist[p]);
    parent[p] = ret.first;
    dist[p] = ret.second - acc;
    return ret;
}
int merge(int a, int b){
    parent[a] = b;
    dist[a] = abs(a-b) % 1000;
    return b;
}
int main() {
    scanf("%d", &T);
    while(T--){
        scanf("%d", &N);
        for(int i = 1; i <= N; i++) parent[i] = i, dist[i] = 0;
        while(1){
            char op;
            scanf("%c ", &op);
            if(op == 'O') break;
 
            if(op == 'E'){
                int I;
                scanf("%d", &I);
                find(I,0);
                printf("%d\n", dist[I]);
            }
            else if(op == 'I'){
                int I,J;
                scanf("%d%d", &I, &J);
                merge(I, J);
            }
        }
    }
    return 0;
}