Bicromia#3165

Bicromia (Editoriale)

Nel problema occorre verificare se sia possibile colorare il grafo con $2$ colori in modo che due vertici adiacenti qualsiasi abbiano colori diversi. Un tale grafo si chiama bipartito.

Se si effettua una ricerca in profondità sul grafo, allora:

Sia il primo vertice di colore $1$ ;
Allora tutti i suoi vicini devono avere colore $2$ ;
I vicini dei vertici di colore $2$ devono nuovamente avere colore $1$ ;
E così via...

Ossia i colori dei vertici devono alternarsi in base alla profondità dell'attraversamento.

Per risolvere il problema utilizzeremo la ricerca in profondità. Inizialmente tutti i vertici sono considerati non visitati e contrassegnati con il colore $0$ . Nel processo di attraversamento del grafo coloreremo i vertici con due colori: $1$ e $2$ . Se il vertice corrente ha colore $i$ (dove $i = 1$ i = 1 oppure $2$ ), allora ogni vertice successivo in cui ci spostiamo durante l'attraversamento in profondità viene colorato con il colore $3 - i$ 3 - i. Allo stesso tempo, a ogni passo verifichiamo che due vertici adiacenti qualsiasi non siano colorati con lo stesso colore.

Esempio

I grafi presentati nell'esempio hanno il seguente aspetto:

Implementazione dell'algoritmo

La matrice di adiacenza del grafo verrà memorizzata in un array $g$ di dimensione $M A X = 1001$ MAX = 1001 (la numerazione dei vertici va da $1$ a $n \leq 1000$ n \le 1000). L'array $u se d$ contiene le informazioni sul colore di ciascun vertice. La variabile globale $f l a g$ è responsabile della correttezza della colorazione: non appena vengono individuati due vertici adiacenti colorati con lo stesso colore, questa variabile assume il valore $1$ .

#define MAX 1000
int g[MAX][MAX], used[MAX], flag;

La funzione dfs esegue la ricerca in profondità. Le vengono passati due parametri: il vertice corrente $v$ e il suo colore $co l or$ .

void dfs(int v, int color = 1)
{

Se in precedenza era già stato rilevato un caso in cui la colorazione richiesta è impossibile ( $f l a g = 1$ flag = 1), l'esecuzione della funzione viene interrotta.

  if (flag) return;

Contrassegniamo il vertice $v$ con il colore color.

  used[v] = color;

Esaminiamo tutti i vertici $i$ in cui è possibile spostarsi dal vertice $v$ , continuando l'attraversamento in profondità.

Se il vertice $i$ non è ancora stato visitato, avviamo da esso la ricerca in profondità, passando alla funzione dfs il colore opposto.
Se il vertice $i$ è già stato visitato, verifichiamo la correttezza della colorazione: se i vertici $v$ e $i$ hanno lo stesso colore, ciò significa una violazione della condizione di bipartizione, e impostiamo $f l a g = 1$ flag = 1.

  for (int i = 1; i \le n; i++)
    if (g[v][i] == 1)
      if (used[i] == 0) dfs(i, 3 - color); else
      if (used[v] == used[i]) flag = 1;
}

Ciclo principale del programma. Leggiamo il numero di vertici $n$ e il numero di lati $l$ del grafo. Azzeriamo la matrice di adiacenza e l'array $u se d$ .

while(scanf("%d %d",&n,&l), n)
{
   memset(g,0,sizeof(g));
   memset(used,0,sizeof(used));

Leggiamo i lati del grafo.

   for(i = 0; i < l; i++)
   {
     scanf("%d %d",&a,&b);
     g[a][b] = g[b][a] = 1;
   }

Azzeriamo la variabile $f l a g$ , e avviamo la ricerca in profondità, iniziando dal primo vertice, dopo avergli assegnato preliminarmente il colore $1$ .

   flag = 0; 
   dfs(1);

In base al valore della variabile $f l a g$ stampiamo il risultato.

   if (flag) printf("NOT BICOLOURABLE.\n");
   else printf("BICOLOURABLE.\n");
}