AOJ 2850 Endless BFS

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2850

解法

01BFSで解いた。
まず、2部グラフだと永遠に終わらないことはわかる。
2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は一生消えない。
そして、そこからどんどん頂点集合が広がっていくことがわかる。

どのタイミングで初めて隣接2頂点が current に入るかは普通に BFS をして、隣接頂点が同じ距離にあることが条件である。
そういう隣接2頂点を見つけたら次からは stable （消えない）状態にうつして、そっちはそっちでBFSをする。
ただし、stable のときの遷移は注意が必要である。例えば今 stable な状態で v にいたとして、隣接頂点 u に移ることを考える。stable な v に至るまでのコストを c1、u の頂点0からの距離を c2 とすると、c1, c2 のパリティが等しいときはコストを0にする（v に至ったタイミングで、u も stable とみなせるから）。
なので、01BFS をすればよいということになる。

stable であるかそうでないかで頂点の数を2倍持っておけばよく、計算量は O(n + m) である。

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    vector<vector<int>> d(n, vector<int>(2, inf));
    d[0][0] = 0;
    deque<tuple<int, int>> que;
    que.emplace_back(0, 0);
    while(!que.empty()) {
        int v, stable;
        tie(v, stable) = que.front(); que.pop_front();
        if(stable == 0) {
            for(auto to : g[v]) {
                if(d[to][0] == d[v][0]) {
                    d[v][1] = d[v][0];
                    que.emplace_back(v, 1);
                }
                if(d[to][0] == inf) {
                    d[to][0] = d[v][0] + 1;
                    que.emplace_back(to, 0);
                }
            }
        } else {
            for(auto to : g[v]) {
                if(d[to][1] != inf) continue;
                if((d[to][0] & 1) == (d[v][1] & 1)) {
                    d[to][1] = d[v][1];
                    que.emplace_front(to, 1);
                } else {
                    d[to][1] = d[v][1] + 1;
                    que.emplace_back(to, 1);
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n; ++i) {
        ans = max(ans, d[i][1]);
    }

    cout << (ans == inf ? -1 : ans) << endl;
}

感想

想定解はもっと賢かった。
最初にグラフ作るタイミングですでに頂点を2倍にしておいて、偶数を表す頂点と奇数を表す頂点間に辺をはる感じだった。そうするとただのBFSやるだけになる。
まあ解けたので良し。