네트워크 연결 - 3780

//3780 - 네트워크 연결
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
 
int Dist(int u, int v)
{
    int ret = (u - v > 0 ? u - v : v - u);
    return ret % 1000;
}
 
struct DisjointSet
{
    vector<int> parent, dist;
 
    DisjointSet(int n) : parent(n), dist(n, 0)
    {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        int par = find(parent[u]);
        dist[u] += dist[parent[u]];
        return parent[u] = par;
    }
 
    void merge(int u, int v)
    {
        dist[u] = Dist(u, v);
        parent[u] = v;
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        cin >> N;
        DisjointSet set(N+1);
        char c;
        while (true)
        {
            cin >> c;
            int u, v;
            if (c == 'E')
            {
                cin >> u;
                set.find(u);
                cout << set.dist[u] << "\n";
            }
            else if (c == 'I')
            {
                cin >> u >> v;
                set.merge(u, v);
            }
            else
                break;
        }
    }
}

 

 

 

 

 

 

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

3780번: 네트워크 연결

 

 

 

 

 

 

네트워크 연결

트리로 모델링이 가능하고, 트리들끼리 합쳐질때, 서브트리의 각각의 노드로부터 루트노드의 거리를 갱신해 주어야 합니다. 2만개의 노드에 최대 2만번 트리들끼리 합쳐지니 빠르게 갱신할 수 있는 방법이 필요한데, 이때 disjointset 자료구조를 변형하면 빠른시간내에 갱신할 수 있겠다 생각했습니다. 마침 find함수는 루트노드를 찾을때까지 계속 위로 올라가는 함수이고, 재귀함수로 짜여져 있으니 재귀함수들이 반환될때 루트노드까지의 거리를 갱신해 준다면, 큰 시간복잡도 차이없이 구할 수 있겠다 싶었습니다.