提出 #66951980

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n): p(n+1), sz(n+1,1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x]==x ? x : p[x] = find(p[x]); }
    int unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return a;
        if (sz[a] < sz[b]) swap(a,b);
        p[b] = a;
        sz[a] += sz[b];
        return a;
    }
};

int main(){
    int N, M;
    cin >> N >> M;

    vector<int> U(M+1), V(M+1);
    for(int i = 1; i <= M; ++i)
        cin >> U[i] >> V[i];

    int Q;
    cin >> Q;
    vector<int> X(Q);
    for(int i = 0; i < Q; ++i)
        cin >> X[i];

    DSU dsu(N);
    vector<unordered_set<int>> adj(N+1);
    for(int i = 1; i <= M; ++i){
        adj[U[i]].insert(V[i]);
        adj[V[i]].insert(U[i]);
    }

    long long edges = M;
    for(int i = 0; i < Q; ++i){
        int idx = X[i];
        int u = dsu.find(U[idx]);
        int v = dsu.find(V[idx]);
        if(u != v && adj[u].count(v)){
            --edges;
            if(adj[u].size() < adj[v].size()) swap(u,v);
            int root = dsu.unite(u, v);
            int other = (root == u ? v : u);
            for(int w: adj[other]){
                if(w == root) continue;
                if(adj[root].count(w)) --edges;
                adj[root].insert(w);
                adj[w].erase(other);
                adj[w].insert(root);
            }
            adj[other].clear();
        }
        cout << edges << "\n";
    }

    return 0;
}

提出情報

ジャッジ結果