BOJ #17398 - 통신망 분할

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, Q, x, y;

int arr[100010], pa[100010];

int find(int n) {
    if (pa[n] < 0)
        return n;
    return pa[n] = find(pa[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    pa[a] += pa[b];
    pa[b] = a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fill(pa, pa + 100010, -1);

    cin >> N >> M >> Q;

    vii v(100010);
    vi p(100010);

    fup(i, 1, M, 1) {
        cin >> x >> y;
        v[i] = pi(x, y);
    }

    fup(i, 1, Q, 1) {
        cin >> x;
        arr[x]++;
        p[i] = x;
    }

    fup(i, 1, M, 1) {
        if (!arr[i]) {
            merge(v[i].first, v[i].second);
        }
    }

    ll ans = 0;
    fdn(i, Q, 1, 1) {
        ll res = pa[find(v[p[i]].first)] * pa[find(v[p[i]].second)];
        if (find(v[p[i]].first) == find(v[p[i]].second))
            res = 0;
        ans += res;
        merge(v[p[i]].first, v[p[i]].second);
    }

    cout << ans;
}