Grafo Bipartido

Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos, de modo que cada aresta conecta dois vértices de conjuntos diferentes (ou seja, não há arestas que conectem vértices do mesmo conjunto). Esses conjuntos são geralmente chamados de lados.

É fornecido um grafo não direcionado. Verifique se é bipartido e, se for, produza seus lados.

Algoritmo

Existe um teorema que afirma que um grafo é bipartido se e somente se todos os seus ciclos tiverem comprimento par. No entanto, na prática, é mais conveniente usar uma formulação diferente da definição: um grafo é bipartido se, e somente se, tiver uma dupla-coloração( graph two-colorable, vértices da mesma cor nunca serão adjacentes ao longo de uma aresta).

Vamos usar uma série de BFS's, começando por cada vértice que ainda não foi visitado. Em cada pesquisa, atribua o vértice a partir do qual começamos ao lado 1. Cada vez que visitamos um vizinho ainda não visitado de um vértice atribuído a um lado, atribuímos ele ao outro lado. Quando tentamos ir a um vizinho de um vértice atribuído a um lado que já foi visitado, verificamos se ele foi atribuído ao outro lado; se foi atribuído ao mesmo lado, concluímos que o grafo não é bipartido. Depois de visitar todos os vértices e atribuí-los com sucesso aos seus lados, sabemos que o grafo é bipartido e assim teremos construído sua partição.

Implementação

int n;
vector<vector<int>> adj;

vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
    if (side[st] == -1) {
        q.push(st);
        side[st] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int u : adj[v]) {
                if (side[u] == -1) {
                    side[u] = side[v] ^ 1
                    q.push(u);
                } else {
                    is_bipartite &= side[u] != side[v];
                }
            }
        }
    }
}

cout << (is_bipartite ? "YES" : "NO") << endl;

Problemas: