Graph Game [CSAcademy #63 D]

https://csacademy.com/contest/round-63/task/graph-game/

N頂点M辺の無向グラフがある。
AlexとBobが戦う。
Alexが先攻。
次数が偶数の頂点とそれにつながる辺を消す操作を行う。
操作が行えなくなったほうが負け。
どちらも適切に動いた時の勝者はどちらか。

本当の解法

Nの偶奇がそのまま答え。
天才。

嘘っぽい本番解法

この無向グラフから何回の操作ができるかを計算する。
奇数回の操作ができれば「Alex」、偶数回の操作ができれば「Bob」の勝ちとなる。
　
嘘解法っぽいけど、このレベル帯ならこれで通るかもと思ってやったら通った解法なのだが、
「どんな風に操作しても最終的な操作回数の偶奇は変わらない」
という仮定を立てた。
　
この仮定が正しいならば適当にシミュレーションをして操作回数を割り出せば、その偶奇を答えとして使って良い。
適当に1パターンシミュレーションをして、数えて偶奇を答えると答え。
シミュレーションは幅優先の様な感じにやっていけばいい。
キューに入れてから取り出す過程で次数が変化したり、既に消されたりする可能性があるので、次数をチェックしたりフラグを立てたりしてやり過ごそう。

int N, M;
set<int> E[101010];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N >> M;
    rep(i, 0, N) E[i].clear();
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].insert(b);
        E[b].insert(a);
    }

    queue<int> q;
    vector<int> vis(N, 0);
    rep(i, 0, N) if (E[i].size() % 2 == 0) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int i = q.front(); q.pop();
        if (vis[i]) continue;
        if (E[i].size() % 2 != 0) continue;
        vis[i] = 1;
        cnt++;

        fore(to, E[i]) {
            E[to].erase(i);
            if (E[to].size() % 2 == 0) q.push(to);
        }
        E[i].clear();
    }

    int ans = cnt % 2;
    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}