Comprobar si un grafo es bipartito
Un grafo bipartito es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos de modo que cada arista conecta dos vértices de conjuntos distintos (es decir, no hay aristas que conecten vértices del mismo conjunto). Estos conjuntos se suelen llamar lados.
Se da un grafo no dirigido. Hay que comprobar si es bipartito y, si lo es, imprimir sus lados.
Algoritmo
Existe un teorema que afirma que un grafo es bipartito si y solo si todos sus ciclos tienen longitud par. Sin embargo, en la práctica es más conveniente usar otra formulación de la definición: un grafo es bipartito si y solo si es 2-coloreable.
Usemos una serie de búsquedas en anchura, empezando desde cada vértice que todavía no fue visitado. En cada búsqueda, asignamos el vértice desde el que empezamos al lado 1. Cada vez que visitamos un vecino todavía no visitado de un vértice asignado a un lado, lo asignamos al otro lado. Cuando intentamos ir a un vecino de un vértice asignado a un lado que ya fue visitado, chequeamos que haya sido asignado al otro lado; si fue asignado al mismo lado, concluimos que el grafo no es bipartito. Una vez que visitamos todos los vértices y los asignamos exitosamente a lados, sabemos que el grafo es bipartito y construimos su partición.
Implementación
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;