Official

C - Bipartize Editorial by en_translator

First let us consider, given a way to paint each of the \(N\) vertices black or white, how we can find the minimum number of edges needed to be removed so that:

  • for every edge, its two endpoint vertices have different colors.

This is equal to the number of edges connecting vertices with the same color, so it can be found in \(O(M)\) time.

The minimum value \(m\) among all \(2 ^ N\) ways to paint the \(N\) vertices is the answer to the original problem.

Proof

For any way of painting, the resulting graph after the removals is bipartite. Thus, \(m\) is not less than the answer to the original problem. (In other words, it is possible to make the graph bipartite by removing \(m\) edges.)

Also, a bipartite graph obtained by an optimal set of operations (with minimum number of removed edges) can be painted black and white so that the condition above is satisfied. Since \(m\) is the minimum value required to be removed among every way of painting, including the painting for that bipartite graph, so \(m\) is not greater than the answer to the original problem. (In other words, it is required to remove at least \(m\) edges to make the graph bipartite.)

Hence, the answer to the original problem has been proved equal to \(m\).

Therefore, the problem has been solved in \(O(2 ^ NM)\) time.

The following is sample code.

#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; // Make indices 0-based
        --v;
    }

    int ans = M;
    // Try all 2^N ways of painting
    for (int bit = 0; bit < 1 << N; ++bit) {
        int delete_count = 0;
        for (const auto& [u, v] : edges) { // Inspect each edge
            if ((1 & (bit >> u)) == (1 & (bit >> v))) // If the endpoints are painted in the same color
                ++delete_count; // increment the count
        }
        ans = min(ans, delete_count); // The answer is the minimum among all ways
    }
    cout << ans << endl;
    return 0;
}

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

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

ans = M
# Try all 2^N ways of painting
for bit in range(2 ** N):
    delete_count = 0
    for u, v in edges: # Inspect each edge
        if (1 & (bit >> u)) == (1 & (bit >> v)): # If the endpoints are painted in the asame color
                delete_count += 1 # increment the count
    ans = min(ans, delete_count)

print(ans)

posted:
last update: