AtCoder ABC 302 E - Isolation (緑色, 425 点)

「要素の削除」をする必要がある場合は set が使えたりする

• 問題へのリンク

問題概要

最初、頂点数 、辺数 のグラフがある。

このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。

• クエリタイプ 1 (1 u v)：頂点 間に辺を張る
• クエリタイプ 2 (2 v)：頂点 に接続する辺をすべて削除する

なお、クエリのどの段階でもグラフは単純無向グラフであることが保証される。

制約

• 
• 

考えたこと

基本的にはグラフを表現するのによく用いる vector<vector<int>> 型を用いればよさそうだが、辺を削除するのが厄介だ。

削除に対応するために、vector<set<int>> 型を用いることにする。つまり、各頂点 に隣接する頂点たちを、set<int> 型で管理するのだ。

また、クエリを終えるたびに「孤立点の個数」をいちいち数えていたのでは間に合わないので、差分のみ更新することにする。

それによって計算量は となる。

コード

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

int main() {
    int N, Q;
    cin >> N >> Q;
    
    int res = N;
    vector<set<int>> G(N);
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            if (G[u].empty()) --res;
            G[u].insert(v);
            if (G[v].empty()) --res;
            G[v].insert(u);
        } else {
            int v;
            cin >> v;
            --v;
            if (!G[v].empty()) ++res;
            for (auto v2 : G[v]) {
                G[v2].erase(v);
                if (G[v2].empty()) ++res;
            }
            G[v].clear();
        }
        cout << res << endl;
    }
}