Time Lapse :NONE

17398.cpp

c++

#include <iostream>
#include <list>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

int n, m, q;
vector<pair<int, int>> edge;
vector<int> group;
vector<int> cnt;
stack<int> st;
unordered_set<int> s;
int n1, n2;
long res(0L);

int find(int n) {
    return group[n] == n ? n : group[n] = find(group[n]);
}

void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if(pa != pb) {
        group[pa] = pb;
        cnt[pb] += cnt[pa];
    }
}

int main() {
    scanf("%d%d%d",&n,&m,&q);
    edge.reserve(m + 1);
    group = vector<int>(n + 1, 0);
    cnt = vector<int>(n + 1, 1);
    edge.push_back({0, 0});
    for(int i = 1; i <= n; i++) group[i] = i;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d",&n1,&n2);
        edge.push_back({n1, n2});
        s.insert(i);
    }

    for(int i = 0; i < q; i++) {
        scanf("%d",&n1);
        st.push(n1);
        s.erase(n1);
    }

    for(auto num : s) {
        merge(edge[num].first, edge[num].second);
    }

    while(!st.empty()) {
        auto p = st.top(); st.pop();

        int pa = find(edge[p].first);
        int pb = find(edge[p].second);

        if(pa == pb) continue;
        res += (1L * cnt[pa] * cnt[pb]);
        merge(pa, pb);
    }

    cout<<res;
}