二部グラフ 復元

[Astral-23]

verifyに使える便利な問題がそうそう無さそうです

vec<int> is_bipartite (const vec<vec<int>> &g) {
    int n = g.size();
    vec<int> col(n, -1);

    auto dfs = [&](auto f, int v, int c) -> void {
        col[v] = c;
        for(int to : g[v]) if(col[to] == -1) {
            f(f, to, c ^ 1);
        }
    };

    for(int i = 0; i < n; i++) if(col[i] == -1) dfs(dfs, i, 0);

    bool ng = false;
    for(int i = 0; i < n; i++) for(int to : g[i]) {
        if(col[i] == col[to]) ng = true;
    }

    if(ng) {
        fill(all(col), -1);
    }
    return col;
}

/*
INPUT: 
{0, ... , n-1}
頂点について、これらを
頂点v を表す = {v, v + n}
の形で管理しているdsu

OUTPUT: 
二部グラフを復元した物: {0, 1}の割り当てを返す。
二部グラフでなければ-1埋め
*/
vec<int> is_bipartite (dsu &uf, int n) {
    vec<vec<int>> gs = uf.groups();
    vec<int> col(n, -1);

    auto id = [&](ll x) {
        if(x < n) return x;
        else return x - n;
    };

    for(auto &vs : gs) if(col[id(vs[0])] == -1) {
        for(auto v : vs) {
            if(v < n) col[v] = 0;
            else col[v - n] = 1;
        }
    }

    for(int i = 0; i < n; i++) if(uf.same(i, i + n)) {
        fill(all(col), -1);
        break;
    }
    return col;
}

前者 : https://codeforces.com/contest/1991/submission/273332004 後者 : https://codeforces.com/contest/1991/submission/273332725