Verifica se è bipartito
Lezione 14 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
Un grafo è bipartito se puoi dividere i suoi vertici in due gruppi in modo che ogni arco colleghi un vertice di un gruppo a un vertice dell’altro. Pensa al rosso e al blu: ogni arco ha un estremo rosso e uno blu.
La BFS offre un test semplice. Parti da un qualsiasi vertice, coloralo di rosso e procedi verso l’esterno. Ogni nuovo vicino riceve il colore opposto a quello del vertice da cui siamo arrivati. Se incontriamo un arco che collega due vertici dello stesso colore, il grafo non è bipartito. Il classico caso problematico è un ciclo di lunghezza dispari: un triangolo 0-1-2-0 costringe il vertice 0 a essere sia rosso sia blu.
Una cosa da ricordare: se il grafo ha più componenti connesse, devi avviare una nuova 2-colorazione per ciascuna. Lo schema più semplice consiste in un unico ciclo su tutti i vertici, che avvia una BFS ogni volta che trova un vertice non colorato.
Sfida
FacileScrivi una funzione isBipartite che riceva un array bidimensionale di interi adjacency e un array di interi vertices, e restituisca true se il grafo è bipartito, false altrimenti.
Costruisci il grafo (esegui addVertex per ciascun vertice, poi addEdge per ciascun arco). Poi assegna due colori tramite BFS su ogni componente connessa: assegna al vertice iniziale il colore 0 e assegna a ogni vicino il colore 1 - color[u]. Se trovi un arco i cui estremi hanno già lo stesso colore, restituisci false. Altrimenti restituisci true.
Devi usare la classe Graph (fornita in graph): non usare le strutture integrate del linguaggio (mappe, insiemi) per rappresentare le adiacenze. I dati ausiliari per l'algoritmo (mappa dei colori, coda) possono usare i tipi della libreria standard.
Provalo tu
#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;
}
Tutte le lezioni di Grafi - Serie sulle strutture dati #9
Esercitati da solo: Compilatore C online