백준 17398 (C++) 통신망 분할

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

17398번: 통신망 분할

 

 

 

 

 

 

아이디어

union find인데 제거할 때 나오는 비용을 세는 대신,

전부 분리한 다음 분리하지 않을 간선만 이은 채로 union을 전부 돌면 된다.

 

전부 서로소 집합인 상태에서 끊지 않을 간선을 제외한 노드들(예제에서는 1,2)을 union할때와

이후 답을 찾기위한 union은 같으나 후자에서는 부모노드 확인과정을 거친 후 비용을 곱해서 저장해야 한다.

 

아이디어는 빨리 떠올렸는데 구현에서 자잘한 실수가 많아 여러번의 제출을 걸쳐 AC를 받은 문제

 

 

 

728x90

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int MAX = 1e6;
int n,m,q;
int Parent[MAX]; // Parent[node] == parent of node
int cost[MAX];
int elem[MAX];
ll ans = 0;
vector<pair<int, int>> c; // 연결노드 저장
vector<int> unc;
bool connect[MAX] = {false, };

int getParent(int n1) {
    if (Parent[n1] == n1) return n1;
    else return Parent[n1] = getParent(Parent[n1]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) {
        Parent[n2] = n1;
        cost[n1] += cost[n2];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; i++) {
        Parent[i] = i;
        cost[i] = 1;
    }
    for (int i = 0; i < m; i++) { // 연결할 간선
        int a,b;
        cin >> a >> b;
        c.push_back({a,b});
        connect[i] = true;
    }
    for (int i = 0; i < q; i++) { // 연결 끊을 간선
        int a;
        cin >> a;
        unc.push_back(a-1);
        connect[a-1] = false;
    }
    for (int i = 0; i < m; i++) { // 끊을 간선이 아니라면 union
        if (!connect[i]) continue;
        unionParent(c[i].first, c[i].second);
    }
    for (int i = q-1; i >= 0; i--) {
        int seq_to_connect = unc[i]; // 4 2 3
        auto node_to_connect = c[seq_to_connect];
        int u = getParent(node_to_connect.first);
        int v = getParent(node_to_connect.second);
        if (u != v) {
            ans += cost[u] * cost[v];
        }
        unionParent(u, v);
    }
    cout << ans;
    return 0;
}