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

문제 출처: https://www.acmicpc.net/problem/17398

17398번: 통신망 분할

해당 문제가 유니온파인드 인 것을 알고 접근했지만 문제에서는 집합을 분리하는 연산을 요구했다.

주어지는 통신탑 간의 연결에서 하나씩 연결을 끊어가며 세는 방법보다는 

주어지는 통신탑 간의 연결에서 모든 연결 끊기 요청을 수행한 상태에서 역순으로 하나씩 병합을 하는 방법을 통해 해결할 수 있었다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>
#include <math.h>

using namespace std;

typedef pair<int, int>P;

P connect[100001];
int disconnect[100001];
int linearDisconnect[100001];

int u[100001];

int find(int a) {
    if (u[a] < 0)return a;
    return u[a] = find(u[a]);
}

unsigned long long merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)return 0;
    if (u[a] < u[b]) {
        int temp = u[a];
        int temp2 = u[b];
        u[a] += u[b];
        u[b] = a;
        return (unsigned long long)temp * (unsigned long long)temp2;
    }
    else {
        int temp = u[a];
        int temp2 = u[b];
        u[b] += u[a];
        u[a] = b;
        return (unsigned long long)temp * (unsigned long long)temp2;
    }
}


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M, Q; cin >> N >> M >> Q;

    fill(&u[0], &u[100001], -1);


    
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        connect[i + 1] = P{ a,b };
    }

    for (int i = 0; i < Q; i++) {
        int temp; cin >> temp;
        linearDisconnect[i] = temp;
        disconnect[temp] = 1;
    }

    for (int i = 1; i <= M; i++) {
        if (disconnect[i] == 1)continue;
        
        merge(connect[i].first, connect[i].second);
    }

    unsigned long long sum = 0;

    for (int i = Q - 1; i >= 0; i--) {
        int idx = linearDisconnect[i];
        unsigned long long val = merge(connect[idx].first, connect[idx].second);
        sum += val;
    }

    cout << sum;
    
}