[C++] 25832번 Making Connections

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

---

 

25/01/01

 

 

약간의 트릭을 가미한 유니온 파인드 문제다.

 

이 문제를 참 많이 틀렸었는데... 허무하게 원인을 찾아버려서 글로도 남겨보고, 복습도 해보고자 한다.

---

 

문제 접근 방식:

 

 

결론적으로 틀린 원인만 말하면 long long이슈다. long long자료형을 써야하는데 int를 써서 값이 이상하게 나왔다.

 

문제는 두 가지 쿼리를 처리해야한다.

 

첫번째로 두 노드를 합치는 연산. 두 노드를 합친다면 두 노드는 같은 그룹에 속해있게 된다.

 

두번째로 그래프의 복잡도를 구하는 연산. 이때 모든 그룹의 크기와 그룹의 개수를 구해야 한다.

 

유파로 처리해보이는건 당연하고, 두번째를 어떻게 빠르게 처리할 지가 의문일 것이다.

 

따라서 나는 그룹의 크기를 저장하는 배열 C를 선언했다. 유니온 파인드를 할 때 대표 노드에 이 크기를 저장하도록 변경해주었다.

 

그러면 그룹의 개수는 어떻게 세어주어야 할까? 2번 쿼리를 받을 때마다 일일히 세어준다면 시간 초과를 받을 것이 뻔한데, $\mathcal{O}(1)$만에 처리를 해주어야 할 것이다.

 

그래프의 복잡도는 각 그룹의 크기가 $g_i$라고 할 때, $(g_{1} ^2 + g_{2} ^2 + \cdots + g_n ^2) / n$으로 정의가 된다.

 

따라서 그래프의 복잡도를 구하는 쿼리를 처리할 때는 그룹의 개수와 각 그룹의 크기만 관리해주면 된다.

 

핵심적인 아이디어는, 서로 다른 두 그룹을 합칠 때는 항상 그룹의 개수가 1만큼 줄어들고, 두 그룹의 크기가 각각 $a, b$라고 한다면 분자가 $a^2 + b^2$에서 $a^2 + 2ab +b^2$으로 바뀌므로 $2ab$만큼 늘어난다는 사실이다.

 

이를 통해 첫 번째 쿼리를 처리할 때마다 그룹의 개수와 각 그룹의 크기의 제곱 합을 바로바로 업데이트 해주면 된다.

 

int로 틀린 이유는 노드의 최대 개수가 $10^5$인데, 제곱을 하면 $10^{10}$이므로 int범위를 넘어가 버린다...

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 25832번 Making Connections
// 유파
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ll;

ll gcd(ll a, ll b){
    ll temp, r;
    if (a < b){
        temp = a;
        a = b;
        b = temp;
    }
    while (b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int find(vector<int>& P, int node){
    if (P[node] != node){
        P[node] = find(P, P[node]);
    }
    return P[node];
}

void merge(vector<int>& C, vector<int>& P, int node1, int node2, ll& U, ll& V){
    int P1 = find(P, node1), P2 = find(P, node2);
    if (P1 != P2){
        V--;// 그룹이 서로 다르다면 합치는 작업 진행. 총 그룹 수는 1개 줄어든다.
        U += 2*(ll)C[P1]*(ll)C[P2]; // 기존에 a^2 + b^2 + ...에서 (a+b)^2 + ...로 바뀜. 2*a*b만큼 늘어남
        if (P1 < P2){
            P[P2] = P1;
            C[P1] += C[P2];
        }
        else {
            P[P1] = P2;
            C[P2] += C[P1];
        }
    }
    return;
}

int main(void){
    fastio;
    int N, M; cin >> N >> M; // the number of computers, the number of query
    vector<int> P(N+1);
    vector<int> C(N+1);
    for (int i=0; i < N+1; i++){
        P[i] = i;
    }
    fill(C.begin(), C.end(), 1);
    int Q, u, v;
    ll U = N, V = N;
    ll G;
    while (M--){
        cin >> Q;
        if (Q == 1){
            cin >> u >> v;
            merge(C, P, u, v, U, V);
        }
        else{
            G = gcd(U, V);
            cout << U/G << '/' << V/G << endl;
        }
    }
    return 0;
}