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

17398번: 통신망 분할

 

문제를 읽어보니 통신망들의 집합을 구현해야 했다.

서로 연결이 되어있는 통신망, 즉 하나의 정점으로 귀납되는 노드들 사이의 한 간선을 끊으면 2개로 나뉠 텐데 몇 개씩으로 나눠지는지를 구하면 된다.

 

풀이 방법을 떠올리기까지 꽤 오래 걸렸는데 처음에 노드의 간선을 끊는 동작을 하나의 쿼리로 보고 세그먼트 트리를 구성해서 풀어야 하나?라는 말만 그럴듯한 이상한 생각을 했다.

 

그러다가 일단 input에 입력을 다 받고 보니 반대로 생각해서 통신망이 주어진대로 다 끊어져 있는 상태에서 끊는 경우의 역순으로 다시 연결한다면 답을 똑같이 구할 수 있지 않을까 생각이 들어서 풀게 되었다. 물론 유니온 파인드를 사용했고 두 집합을 연결하기 전에 각각 몇 개의 노드가 연결되어있는지는 node[]에 -1을 곱하면 알 수 있으므로 쉽게 구할 수 있다. (node배열을 -1로 초기화했기 때문임)

 

#include <iostream>
#include <vector>
#include <deque>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
typedef long long ll;
 
using namespace std;
 
int N, M, Q;
ll ans;
 
deque<int> Q_list;
vector<pii > link_list;
bool isuse[100001];
int node[100001];
 
void input(){
    cin >> N >> M >> Q;
    int u, v;
    for(int i = 0; i < M; i++){
        cin >> u >> v;
        link_list.push_back({u, v});
    }
    for(int i = 0; i < Q; i++){
        cin >> u;
        Q_list.push_front(u);
        isuse[u] = true;
    }
    memset(node, -1, sizeof(node));
}
 
int findtopnode(int a){
    if(node[a] < 0) return a;
    return node[a] = findtopnode(node[a]);
}
 
ll Union_node(int a, int b){
    a = findtopnode(a);
    b = findtopnode(b);
    
    if(a == b) return 0;
    
    ll ret = node[a] * node[b];
    
    if(node[a] < node[b]){
        node[a] += node[b];
        node[b] = a;
    }
    else{
        node[b] += node[a];
        node[a] = b;
    }
    
    return ret;
}
 
void solve(){
    // 통신망이 연결됨을 확인하는 방법 : 분리 집합?
    
    // 연결을 끊었을 때 두 개로 나눠짐을 어떻게 파악하지?
    // 끊어질 때마다 처음부터 유니온 파인드 실행?? 절대 안됨
    // 세그먼트 트리??
    // 연결을 끊는다는걸 하나의 쿼리로 생각?
    
    // 1. 분리 집합의 최적화..
    // 쿼리는 최대 10만개
    // 연결도 최대 10만개
    // 아 미리 제거해놓고 제거 역순으로 다시 연결시키면서
    // 연결될 때 서로 몇개의 원소를 가지고 연결되는지 확인
    
    for(int i = 0; i < link_list.size(); i++){
        if(isuse[i+1]) continue;
        int u = link_list[i].first;
        int v = link_list[i].second;
        Union_node(u, v);
    }
    
    for(auto &q: Q_list){
        int u = link_list[q-1].first;
        int v = link_list[q-1].second;
        ans += Union_node(u, v);
    }
    
    
    cout << ans;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}