[c++] 백준 #17398 통신망 분할 (190826)

< 풀이 >

연결된 애를 쪼개는 것에 대해 물어보는 문제였는데, 반대로 쪼개져 있는 애들을 합치는 방식으로 disjoint set으로 구현한다.(신기..) 그래프를 union할 때마다 각 set의 원소의 개수를 서로 곱해서 cost를 더해준 다음에 빼주면 됨. 이때 원소의 개수를 어떻게 count할 지가 고민이었는데 모두 다 1로 초기화한 다음에 union할 때마다 부모(대빵) 노드 기준으로만 자기 밑에 원소 몇 개 있는 지 더해주면 된다.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define N_MAX 100010
int p[N_MAX];
vector<int> n_elem; // 각 집합의 원소 수를 계산
vector<ii> connections; // 노드 연결 정보
vector<int> NotConnectedlist; // 안 연결되는 connection의 번호를 저장
int isNotConnected[N_MAX]; // 연결 여부를 bool로(굳이 그냥 빠르게 연산하려고)
ll cost;

int N, M, Q;

int my_find(int u){
    if (p[u]==u) return u;
    else {
        return p[u] = my_find(p[u]);
    }
}

void my_union(int u, int v){
    int u_root = my_find(u);
    int v_root = my_find(v);
    if (u_root != v_root) {
        p[u_root] = v_root;
        cost += n_elem[u_root]*n_elem[v_root];
        n_elem[v_root] += n_elem[u_root];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> Q;
    n_elem = vector<int>(N+1, 1); // 각 노드를 root로 하는 set의 원소 수를 count
    // 부모 배열 초기화
    for(int i=0; i<=N;i++){
        p[i] = i;
    }
    // get connections info
    for(int i=0; i<M;i++){
        int a, b;
        cin >> a >> b;
        connections.push_back(make_pair(a-1,b-1));
    }
    // 안연결하는 애들 정보 저장
    while(Q--){
        int n_c;
        cin >> n_c; 
        NotConnectedlist.push_back(n_c-1); // 0~ M-1
        isNotConnected[n_c-1] = true;
    }
    // 나머지 정보로 그래프 구성
    for(int i=0; i<M;i++){
        if (isNotConnected[i]) continue;
        else {
            auto item = connections[i];
            int u = item.first;
            int v = item.second;
            my_union(u,v);
        }
    }
    ll temp = cost;
    // 안 연결된 애들을 뒤에서부터 하나씩 
    int len = NotConnectedlist.size();
    for(int i=0; i<len;i++){
        int c_number = NotConnectedlist[len-1-i];
        auto item = connections[c_number];
        int u = item.first;
        int v = item.second;
        my_union(u,v);
    }
    cout << cost - temp << '\n';
    return 0;
}