Перевертання карт#7538

Перевертання карт (Розбір)

Кожній картинці, зображеній на картах, поставимо у відповідність вершину графа. Кожній карті поставимо у відповідність неорієнтоване ребро, що з'єднує вершини, відповідні зображенням на її сторонах. Отриманий граф може бути незв'язним.

Відповідь на задачу буде possible, якщо в кожній компоненті зв'язності графа міститься не більше одного циклу. Компоненти зв'язності та кількість циклів у них можна визначити за допомогою системи неперетинних множин.

Приклад

Розглянемо чотири карти. Жовтим позначимо сторони карт, що звернені вгору. Кожному ребру графа поставимо у відповідність картинку, якою відповідна карта лежить вгору.

Розглянемо випадок з двома компонентами зв'язності:

Реалізація алгоритму

Визначимо масиви для обробки даних. Масив $d s u$ використовується для системи неперетинних множин. Якщо $i$ — представник множини, то $ha s_cy c l e [i]$ has\_cycle[i] містить інформацію про кількість циклів у ній:

$ha s_cy c l e [i] = 0$ has\_cycle[i] = 0, циклів немає;
$ha s_cy c l e [i] = 1$ has\_cycle[i] = 1, є один цикл;
$ha s_cy c l e [i] > 1$ has\_cycle[i] > 1, є більше одного циклу;

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

Функція Repr повертає представника множини, що містить вершину $n$ .

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

Функція Union об'єднує множини, що містять вершини $x$ та $y$ .

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

Якщо вершини $x$ та $y$ вже належать одній компоненті зв'язності (вони мають однакового представника), і при цьому додається ребро $(x, y)$ , то утворюється ще один цикл. У цьому випадку збільшуємо кількість циклів у представника цієї множини ( $x_{1}$ x_1 — представник $x$ та $y$ ):

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

Якщо $x$ та $y$ належать різним компонентам зв'язності, то виконуємо їх об'єднання, при цьому представник $y_{1}$ y_1 стає представником об'єднаної множини. У цьому випадку до кількості циклів компоненти з коренем $y_{1}$ y_1 додаємо кількість циклів компоненти з коренем $x_{1}$ x_1.

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

Основна частина програми. Читаємо вхідні дані.

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

Ініціалізуємо систему неперетинних множин.

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

Будуємо систему неперетинних множин.

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

Перевіряємо, чи існує хоча б одна компонента зв'язності, що містить більше одного циклу.

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

Виводимо відповідь.

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