[백준] 17398 - 통신망 분할

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

17398번: 통신망 분할

 

일반적인 union-find 문제와 다르게, 이 문제는 이미 연결되어 있는 간선들을 제거할 때 발생하는 비용을 구하는 문제이다.

모든 간선들을 연결하고 하나씩 제거하면서 비용을 계산하는 것은 너무 오랜 시간이 걸리므로, 다른 방법을 강구해 보자.

 

핵심은 제거된 순서의 역순으로 다시 잇는 것이다.

이 경우,

1. 연결하려는 두 정점이 이미 연결되어 있으면 비용은 발생하지 않는다.
2. 연결하려는 두 정점이 연결되어 있지 않으면 각 정점이 포함된 그래프의 정점의 개수의 곱만큼 비용이 발생된다.

 

1번의 경우 때문에, q개의 입력으로 주어진 간선 외의 간선은 미리 연결해주어야 한다.

2번의 경우 때문에, 각 정점이 포함된 그래프의 정점의 개수를 미리 알고 있어야 한다.

 

#include <iostream>
using namespace std;

int n, m, q;
pair<int, int> inp[100001];
int disconnect[100001], p[100001], notPreConnected[100001];
long long ans, cnt[100001];

int Find(int x) {
    if (p[x] == x) {
        return x;
    }
    return p[x] = Find(p[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a < b) {
        p[b] = a;
    } else {
        p[a] = b;
    }
    ans += cnt[a] * cnt[b];
    cnt[a] += cnt[b];
    cnt[b] = cnt[a];
}

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

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        cnt[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        cin >> inp[i].first >> inp[i].second;
    }
    for (int i = 0; i < q; i++) {
        cin >> disconnect[i];
        notPreConnected[disconnect[i]] = 1;
    }
    for (int i = 1; i <= m; i++) {
        if (notPreConnected[i] == 0) {
            int n1 = Find(inp[i].first);
            int n2 = Find(inp[i].second);
            if (n1 != n2) {
                Union(n1, n2);
            }
        }
    }
    ans = 0;

    for (int i = q - 1; i >= 0; i--) {
        int n1 = Find(inp[disconnect[i]].first);
        int n2 = Find(inp[disconnect[i]].second);

        if (n1 != n2) {
            Union(n1, n2);
        }
    }

    cout << ans;
}