Kiểm tra đồ thị hai phía (Bipartite) bằng DFS trong C++

Cho đồ thị liên thông, kiểm tra xem có phải đồ thị hai phía (bipartite) hay không. Đồ thị hai phía có thể tô màu các đỉnh bằng 2 màu sao cho không có cạnh nào nối hai đỉnh cùng màu.

Ví dụ: Đồ thị chu trình 6 đỉnh (1-2-3-4-5-6-1) → True (là bipartite vì chu trình chẵn).

Giải thuật DFS:

• Từ đỉnh xuất phát, gán màu 0.
• Duyệt các đỉnh kề: nếu chưa thăm, gán màu ngược lại và đệ quy; nếu đã thăm và cùng màu → không bipartite.
• Trả về true nếu không phát hiện xung đột.

Ví dụ (C++)

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

void insert_edge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
    for (int u : adj[v]) {
        if (!visited[u]) {
            visited[u] = true;
            color[u] = !color[v];
            if (!is_bipartite_graph(adj, u, visited, color)) return false;
        }
        else if (color[u] == color[v]) return false;
    }
    return true;
}

int main() {
    int N = 6;
    vector<int> adj_list[N + 1];
    vector<bool> visited(N + 1);
    vector<int> color(N + 1);
    insert_edge(adj_list, 1, 2);
    insert_edge(adj_list, 2, 3);
    insert_edge(adj_list, 3, 4);
    insert_edge(adj_list, 4, 5);
    insert_edge(adj_list, 5, 6);
    insert_edge(adj_list, 6, 1);
    visited[1] = true;
    color[1] = 0;
    cout << (is_bipartite_graph(adj_list, 1, visited, color));
}

Đầu vào

Các cạnh: 1-2, 2-3, 3-4, 4-5, 5-6, 6-1

Đầu ra

1