Submission #66977023

---

Source Code Expand

#include <bits/stdc++.h>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<int> u(m), v(m);
    std::vector<std::set<int>> adj(n);
    for (int i = 0; i < m; i++) {
        std::cin >> u[i] >> v[i];
        u[i]--;
        v[i]--;

        adj[u[i]].insert(v[i]);
        adj[v[i]].insert(u[i]);
    }

    std::vector<int> par(n);
    std::iota(par.begin(), par.end(), 0);

    auto find = [&](int x) {
        auto dfs = [&](auto &&self, int x) -> int {
            if (x == par[x]) {
                return x;
            } else {
                return self(self, par[x]);
            }
        };
        return dfs(dfs, x);
    };

    auto same = [&](int x, int y) { return find(x) == find(y); };

    int ans = m;

    auto merge = [&](int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (adj[x].size() < adj[y].size()) {
            std::swap(x, y);
        }
        adj[x].erase(y);
        adj[y].erase(x);
        ans -= adj[x].size() + adj[y].size();
        for (auto y : adj[y]) {
            if (!same(x, y)) {
                adj[x].insert(find(y));
            }
        }
        ans += adj[x].size();
        adj[y].clear();
        par[y] = x;
        return true;
    };

    int q;
    std::cin >> q;

    while (q--) {
        int i;
        std::cin >> i;
        i--;

        int x = u[i], y = v[i];
        merge(x, y);

        std::cout << ans - 1 << "\n";
    }

    return 0;
}

Submission Info

Judge Result