AtCoder Beginner Contest 264E

ABC264E

Union-find, クエリ先読み，クエリの逆算．

切断するのは難しいが，結合するのは Union-find を用いれば簡単． クエリを先読みして，逆算すれば結合に書き換えられる．

実装
\(M\) 個の発電所は，役割がすべて同じなので区別する必要がない． よって，一つの頂点だと思っておくと良い． 問題によっては，超頂点を用意して，超頂点から \(M\) 個の発電所に辺を張る という実装も考えられる．
答えを配列に入れていくが，クエリの開始時点の状態または終了時点を追加することで， \(Q+1\) の長さにすると楽．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m , e;

  cin >> n >> m >> e;

  vector<pll> ed(e);

  rep(i,e){

    ll a,b; cin >> a >> b;

    --a,--b;

    chmin(a, n);

    chmin(b, n);

    ed[i] = {a,b};

  }

 

  ll q; cin >> q;

  vector<bool> con(e, true);

  vll qv;

  rep(qi,q){

    ll x; cin >> x;

    x--;

    qv.push_back(x);

    con[x] = false;

  }

  reverse(all(qv));

  UnionFind<ll> uf(n+1);

  rep(i,e) if(con[i]){

    auto [a,b] = ed[i];

    uf.merge(a,b);

  }

  vll ans; // 開始時の答えも含めて，サイズ q + 1 にした方が楽．

  ans.push_back(uf.size(n));

  for(auto x:qv){

    auto [a,b] = ed[x];

    assert(con[x] == false);

    uf.merge(a,b);

    con[x] = true;

    ans.push_back(uf.size(n));

  }

  reverse(all(ans));

  rep1(i,q) cout << ans[i]-1 << endl;

  return 0;

}