早稲田大学プログラミングコンテスト2019 C - Permutation City

C - Permutation City

木の方が扱いやすそうなので、全域木に変換して0を根とする

dfs(i,親)で以下を繰り返す

iと子のうち、他の頂点に選ばれていない物の集合Vを考える

Vの要素数が1以下ならreturn

2つ以上あればv[0] -> v[1] ......v[last] -> v[0]の様に(i,pi)を対応付ける

上の操作の後、対応が取れていない可能性があるのはp0のみである

その場合、0と繋がる頂点tでp0 = pt , pt  = 0とすればいい

Submission #4548493 - 早稲田大学プログラミングコンテスト2019

undigraph<> g(2 * k5);
vi res;
vi used(k5 * 2);
void ds(int i, int p) {
//親を除く、行き先を走査
    fort(gi, g[i])ds(t, i);
    vi v;
    if (!used[i])v += i;
    fort(gi, g[i]) {
        if (!used[t])v += t;
    }
    if (!used[i]) v += i;
    if (sz(v) < 3) {
        return;
    }
    rep(j, sz(v) - 1) {
        used[v[j]] = 1;
        res[v[j]] = v[j + 1];
    }
}
void solve() {
    cin >> n >> m;
    UnionFind uni(k5 * 2);
    rep(i, m) {
        int f, t;
        cin >> f >> t;
        --f, --t;
        if (uni.same(f, t))con;
        uni.unite(f, t);
        g.add(f, t);
    }
    res.assign(n, -1);
    ds(0, -1);
    if (res[0] == -1) {
        int t = g[0][0].to;
        res[0] = res[t];
        res[t] = 0;
    }
    inc(res);
    cout << res << endl;
}