Chương trình C++ tô màu đồ thị hai phía (Bipartite Graph)

Đồ thị hai phía (Bipartite) là đồ thị có thể chia tập đỉnh thành 2 tập độc lập sao cho mọi cạnh nối một đỉnh tập này với đỉnh tập kia. Tương đương: có thể tô màu đỉnh bằng 2 màu sao cho không có cạnh nào nối hai đỉnh cùng màu.

Thuật toán: BFS 2-coloring

1. Chọn đỉnh bất đầu, tô màu 0 (Vàng).
2. BFS: các đỉnh kề tô màu 1 (Xanh).
3. Tiếp tục: đỉnh kề của màu 1 tô màu 0, xen kẽ.
4. Nếu gặp xung đột (đỉnh kề cùng màu) → không phải bipartite.

Ví dụ mã

#include <bits/stdc++.h>
using namespace std;

int n, e;
vector<vector<int>> g;
vector<int> color; // -1: chưa tô, 0: Vàng, 1: Xanh
vector<bool> visited;

void bfsColor(int start) {
    queue<int> q;
    color[start] = 0;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (!visited[v]) {
                color[v] = 1 - color[u]; // màu đối lập
                visited[v] = true;
                q.push(v);
            } else if (color[v] == color[u]) {
                cout << "Đồ thị KHÔNG phải bipartite (xung đột tại " << u << "-" << v << ")\n";
                exit(0);
            }
        }
    }
}

int main() {
    cout << "Số đỉnh và cạnh: "; cin >> n >> e;
    g.resize(n);
    color.assign(n, -1);
    visited.assign(n, false);

    cout << "Nhập " << e << " cạnh (1-based):\n";
    for (int i = 0; i < e; ++i) {
        int u, v; cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Xử lý nhiều thành phần liên thông
    for (int i = 0; i < n; ++i)
        if (!visited[i]) bfsColor(i);

    cout << "Kết quả tô màu (Y=Vàng, B=Xanh):\n";
    for (int i = 0; i < n; ++i)
        cout << i+1 << " " << (color[i] ? 'B' : 'Y') << '\n';

    return 0;
}

Kết quả mẫu

Số đỉnh và cạnh: 4 3
Nhập 3 cạnh (1-based):
1 2
3 2
4 2
Kết quả tô màu (Y=Vàng, B=Xanh):
1 Y
2 B
3 B
4 B

Đỉnh 2 kết nối với 1,3,4 → tô màu B, các đỉnh còn lại tô Y. Hợp lệ bipartite.