17398 - 통신망 분할

step 1

원래 상태에서 연결을 끊는다고 생각하지 말고 이미 연결을 다 끊어놓은 상태에서 거꾸로 연결을 한다고 생각합니다.

step 2

$Q$번의 연결을 다 끊어놓은 상태를 구할 수 있습니다. 유니온 파인드를 이용해서 어떤 정점들이 이어져 있는지 확인합니다. 그 상태에서 쿼리를 반대로 봅니다. 두 정점이 같은 집합에 있다면 해당 쿼리를 실행했을 때 통신망이 나뉘어지지 않았다는 뜻입니다. 두 정점이 다른 집합에 있다면 각 집합의 크기를 곱한 값만큼 비용이 발생했다는 뜻입니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
struct data {
    long long int x, y;
}b[200000];
long long int tr[200000];
long long int lv[200000], cnt[200000], p[200000],ch[200000];
long long int merge(long long int x, long long int y) {
    while (x != p[x]) x = p[x];
    while (y != p[y]) y = p[y];
    if (x == y) return 0;
    long long int v = cnt[x] * cnt[y];
    if (lv[x] < lv[y]) {
        p[x] = p[y];
        cnt[y] += cnt[x];
    }
    else if (lv[x] > lv[y]) {
        p[y] = p[x];
        cnt[x] += cnt[y];
    }
    else {
        p[y] = p[x];
        cnt[x] += cnt[y];
        lv[x]++;
    }
    return v;
}
int main() {
    long long int n, m, q, i,countt=0;
    scanf("%lld%lld%lld", &n, &m, &q);
    for (i = 1;i <= m;i++) {
        scanf("%lld%lld", &b[i].x, &b[i].y);
    }
    for (i = 1;i <= q;i++) {
        scanf("%lld", &tr[i]);
        ch[tr[i]] = 1;
    }
    for (i = 1;i <= n;i++) {
        lv[i] = 1;
        cnt[i] = 1;
        p[i] = i;
    }
    for (i = 1;i <= m;i++) {
        if (ch[i] == 0) {
            merge(b[i].x, b[i].y);
        }
    }
    for (i = q;i >= 1;i--) {
        countt += merge(b[tr[i]].x, b[tr[i]].y);
    }
    printf("%lld", countt);
    return 0;
}