AtCoder Grand Contest 013: B - Hamiltonish Path

,

http://agc013.contest.atcoder.jp/tasks/agc013_b

出力を$1$-basedにするのを忘れて$1$WA。サンプルと単純比較では検証できないタイプの問題だったので気付けなかった。

solution

適当な頂点から始めて伸ばせる限り単純パスを伸ばして、伸ばせなくなったら答え。$O(N + M)$。 単純パスを伸ばせないということはその端点に隣接する頂点が全てパスに含まれているということであるので。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    vector<bool> used(n);
    vector<int> path;
    function<void (int)> go = [&](int i) {
        path.push_back(i);
        used[i] = true;
        for (int j : g[i]) if (not used[j]) {
            go(j);
            break;
        }
    };
    go(0);
    reverse(whole(path));
    assert (path.back() == 0);
    used[0] = false;
    path.pop_back();
    go(0);
    // output
    printf("%d\n", int(path.size()));
    repeat (i, path.size()) {
        printf("%d%c", path[i] + 1, i + 1 == path.size() ? '\n' : ' ');
    }
    return 0;
}