É Bipartido
Lição 14 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
Um grafo é bipartido se você puder dividir seus vértices em dois grupos de modo que cada aresta conecte um vértice de um grupo a um vértice do outro. Pense em vermelho e azul: cada aresta tem uma extremidade vermelha e uma extremidade azul.
A BFS fornece um teste limpo. Comece em qualquer vértice, pinte-o de vermelho e caminhe para fora. Cada novo vizinho recebe a cor oposta do vértice de onde viemos. Se algum dia virmos uma aresta que conecta dois vértices com a mesma cor, o grafo não é bipartido. O ofensor clássico é um ciclo de comprimento ímpar: um triângulo 0-1-2-0 força o vértice 0 a ser vermelho e azul ao mesmo tempo.
Uma coisa a lembrar: se o grafo tiver múltiplas componentes conexas, você terá que iniciar uma nova coloração de 2 cores em cada uma. O padrão mais fácil é um loop único sobre todos os vértices que inicia uma BFS sempre que encontra um vértice não colorido.
Desafio
FácilEscreva uma função isBipartite que recebe um array de inteiros 2D adjacency e um array de inteiros vertices, e retorna true se o grafo for bipartido, e false caso contrário.
Construa o grafo (addVertex para cada um, depois addEdge para cada um). Em seguida, realize a coloração com 2 cores via BFS sobre cada componente conectado: atribua a cor inicial 0, e dê a cada vizinho a cor 1 - color[u]. Se você encontrar uma aresta onde ambos os pontos extremidade já possuem a mesma cor, retorne false. Caso contrário, retorne true.
Você deve usar a classe Graph (fornecida em graph) - não use recursos nativos da linguagem (maps, sets) para modelar a adjacência. Dados auxiliares para o algoritmo (mapa de cores, fila) podem usar tipos da biblioteca padrão (stdlib).
Experimente você mesmo
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}