公式

C - Bipartize 解説 by MMNMM

まず、\(N\) 個の頂点をそれぞれ白か黒で塗る方法を固定して、次の条件を満たすために削除する必要がある辺の本数を求める問題を考えます。

  • どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。

これは、同じ色の頂点を結んでいる辺の本数と等しいため、\(O(M)\) 時間で求めることができます。

これを \(N\) 頂点の塗り方 \(2 ^ N\) 通りすべてに対して求めたときの最小値 \(m\) がもとの問題の答えになります。

証明

どのような塗り方に対しても、上記の条件を満たすように辺を削除したあとに得られるグラフは二部グラフになっています。 よって、\(m\) はもとの問題の答え以上です（つまり、\(m\) 本削除することで二部グラフにすることができる）。

また、最適な（削除する辺の本数が最小であるような）操作で得られた二部グラフは、適切に白と黒で頂点を塗り分けることで上の条件を満たすようにすることができます。 \(m\) はこの塗り方も含めたすべての塗り方にわたって削除する必要がある辺の本数の最小値を求めているため、\(m\) はもとの問題の答え以下です（つまり、二部グラフにするためには \(m\) 本以上削除する必要がある）。

以上より、もとの問題の答えが \(m\) と等しいことが示されました。

よって、\(O(2 ^ NM)\) 時間でこの問題を解くことができました。

実装例は以下のようになります。

#include <iostream>
#include <utility>
#include <vector>

int main() {
    using namespace std;
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> edges(M);
    for (auto&& [u, v] : edges) {
        cin >> u >> v;
        --u; // 0-indexed にしておく
        --v;
    }

    int ans = M;
    // 2^N 通りの塗り方を全部探索する
    for (int bit = 0; bit < 1 << N; ++bit) {
        int delete_count = 0;
        for (const auto& [u, v] : edges) { // それぞれの辺を見て
            if ((1 & (bit >> u)) == (1 & (bit >> v))) // 結んでいる頂点が同じ色で塗られていたら
                ++delete_count; // カウントを増やす
        }
        ans = min(ans, delete_count); // 全部の塗り方にわたる最小値が答え
    }
    cout << ans << endl;
    return 0;
}

N, M = map(int, input().split())

edges = [tuple(map(int, input().split())) for _ in range(M)]

ans = M
# 2^N 通りの塗り方を全部探索する
for bit in range(2 ** N):
    delete_count = 0
    for u, v in edges: # それぞれの辺を見て
        if (1 & (bit >> u)) == (1 & (bit >> v)): # 結んでいる頂点が同じ色で塗られていたら
                delete_count += 1 # カウントを増やす
    ans = min(ans, delete_count)

print(ans)

投稿日時:
最終更新: