Il ribaltamento delle carte (Editoriale)

A ogni immagine raffigurata sulle carte associamo un vertice del grafo. A ogni carta associamo un arco non orientato, che collega i vertici corrispondenti alle immagini sui suoi lati. Il grafo ottenuto può risultare non connesso.

La risposta al problema sarà possible se in ogni componente connessa del grafo è contenuto non più di un ciclo. Le componenti connesse e il numero di cicli in esse possono essere determinati mediante una struttura union-find (sistema di insiemi disgiunti).

Esempio

Consideriamo quattro carte. Indichiamo in giallo i lati delle carte rivolti verso l'alto. A ogni arco del grafo associamo l'immagine con cui la carta corrispondente giace rivolta verso l'alto.

Consideriamo il caso con due componenti connesse:

Implementazione dell'algoritmo

Definiamo gli array per l'elaborazione dei dati. L'array $dsu$ viene utilizzato per la struttura union-find. Se $i$ è il rappresentante di un insieme, allora has\_cycle[i] contiene l'informazione sul numero di cicli in esso:

• has\_cycle[i] = 0, non ci sono cicli;

• has\_cycle[i] = 1, è presente un ciclo;

• has\_cycle[i] > 1, sono presenti più di un ciclo;

#define MAX 50010
int dsu[2*MAX], has_cycle[2*MAX];

La funzione Repr restituisce il rappresentante dell'insieme contenente il vertice $n$.

int Repr(int n)
{
  if (n == dsu[n]) return n;
  return dsu[n] = Repr(dsu[n]);
}

La funzione Union unisce gli insiemi contenenti i vertici $x$ e $y$.

void Union(int x, int y)
{
  int x1 = Repr(x), y1 = Repr(y);

Se i vertici $x$ e $y$ appartengono già alla stessa componente connessa (hanno lo stesso rappresentante), e allo stesso tempo viene aggiunto l'arco $(x,y)$, allora si forma un ulteriore ciclo. In questo caso incrementiamo il numero di cicli del rappresentante di questo insieme (x_1 è il rappresentante di $x$ e $y$):

  if (x1 == y1)
    has_cycle[x1]++;

Se $x$ e $y$ appartengono a componenti connesse diverse, eseguiamo la loro unione, in cui il rappresentante y_1 diventa il rappresentante dell'insieme unito. In questo caso al numero di cicli della componente con radice y_1 aggiungiamo il numero di cicli della componente con radice x_1.

  else
  {
    dsu[x1] = y1;
    has_cycle[y1] += has_cycle[x1];
  }
}

Parte principale del programma. Leggiamo i dati di input.

scanf("%d",&tests);
while (tests--)
{
  scanf("%d",&n);

Inizializziamo la struttura union-find.

  for(i = 1; i <= 2*n; i++)
  {
    dsu[i] = i;
    has_cycle[i] = 0;
  }

Costruiamo la struttura union-find.

  for (i = 0; i < n; i++) 
  {
    scanf("%d %d",&p,&q);
    Union(p,q);
  }

Verifichiamo se esiste almeno una componente connessa contenente più di un ciclo.

  for (i = 1; i <= 2*n; i++)
    if (has_cycle[i] > 1) break;

Stampiamo la risposta.

  printf("%s\n",((i <= 2 * n) ? "impossible" : "possible"));
}