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

問題

色A, B, C で与えられたグラフを次の条件を満たすように彩色する問題を考える。

AとBで彩色された頂点は、辺で直接繋がっていない。
同じ色で彩色された頂点は、辺で直接繋がっていない。
Aで彩色された頂点とBで彩色された頂点の個数は等しい。

以上の条件を満たして彩色できるとき、Aで彩色できる頂点の数を列挙する。

解法

一見、取っ掛かりが無いので1頂点選んでAで彩色してみます。(AはCに比べて条件が厳しいので, 別にBでもいいです)
すると隣接する頂点は、全てCで塗らなければならないことがわかります。
次に、Cで彩色した頂点に隣接する未彩色の頂点について考えると、AかBで彩色出来ることがわかります。
また、AとBの彩色数は等しいことが要求されていたことを思い出すと次は、Bで彩色したくなります。

ここで、AとBを同一視した色Dを考えます。すると、Cに隣接する頂点はDに彩色され、Dに隣接する頂点はCに彩色されることになります。
つまり、開始地点の色を決定すると全ての頂点の彩色状態が決定するような問題だということがわかります。
また、このことから彩色状態は高々2パターンしか存在しないということもわかりました。

先ほど考えた色Dの中で辻褄が合うように塗り分ければよいので、Aで彩色した後はBで、Bで彩色した後はAで彩色していけば良い事がわかります。

以上を適当な点を始点とした幅優先探索を利用して実現すれば計算量も十分に間に合いそうです。
ただし、3つの頂点が3つの頂点でサイクルを形成しているようなグラフなどは、条件2に触れてしまうので、彩色したあとのグラフに対して別途チェックを書く必要があります。

コード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4899936#1

int n, m;

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

    function<int(int, int)> bfs = [&](int start, int init_color) {
        queue<int> que;
        que.push(start);
        vector<int> color(n, -1);
        color[start] = init_color;

        int x = 0, y = 0;
        if (init_color == 1) x++;

        while (que.size() != 0) {
            int v = que.front();
            que.pop();

            for (auto nv : G[v]) {
                if (color[nv] != -1) continue;

                if (color[v] == 0) {
                    if (x == y) x++;
                    else y++;
                    color[nv] = 1;
                }
                else {
                    color[nv] = 0;
                }

                que.push(nv);
            }
        }


        int ret = x;
        for (int i = 0; i < n; i++) {
            for (auto nv : G[i]) {
                if (color[i] == color[nv]) ret = -1;
            }
        }

        if (x != y) ret = -1;

        return ret;
    };

    set<int> ans;
    int res = bfs(0, 0);
    if (res != -1) ans.insert(res);
    res = bfs(0, 1);
    if (res != -1) ans.insert(res);

    cout << ans.size() << endl;
    for (auto x : ans) cout << x << endl;
}


int main() {
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        solve();
    }
}

yrfw

模擬国内2018E: 分割統治

問題

解法

コード