Es bipartito
Lección 14 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
Un grafo es bipartito si puedes dividir sus vértices en dos grupos de modo que cada arista conecte un vértice de un grupo con un vértice del otro. Piensa en rojo y azul: cada arista tiene un extremo rojo y un extremo azul.
BFS proporciona una prueba clara. Comienza en cualquier vértice, coloréalo de rojo y avanza hacia afuera. Cada nuevo vecino recibe el color opuesto al del vértice del que venimos. Si alguna vez vemos una arista que conecta dos vértices con el mismo color, el grafo no es bipartito. El infractor clásico es un ciclo de longitud impar: un triángulo 0-1-2-0 obliga al vértice 0 a ser tanto rojo como azul.
Una cosa a recordar: si el grafo tiene múltiples componentes conectadas, debes comenzar una nueva coloración de 2 colores en cada una. El patrón más sencillo es un único bucle sobre todos los vértices que inicia un BFS cada vez que encuentra un vértice sin colorear.
Desafío
FácilEscribe una función isBipartite que reciba un array bidimensional de enteros adjacency y un array de enteros vertices, y devuelva true si el grafo es bipartito, o false en caso contrario.
Construye el grafo (usando addVertex para cada uno, luego addEdge para cada uno). Luego, realiza un coloreo con 2 colores mediante BFS sobre cada componente conectada: asigna el color inicial 0 y otorga a cada vecino el color 1 - color[u]. Si alguna vez encuentras una arista donde ambos extremos ya tienen el mismo color, devuelve false. De lo contrario, devuelve true.
Debes utilizar la clase Graph (proporcionada en graph); no utilices elementos integrados del lenguaje (mapas, conjuntos) para modelar la adyacencia. Los datos auxiliares para el algoritmo (mapa de colores, cola) pueden utilizar tipos de la biblioteca estándar (stdlib).
Pruébalo tú mismo
#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;
}