Kartların çevrilməsi (Həll təhlili)

Kartlarda təsvir olunan hər bir şəklə qrafın bir təpəsini uyğunlaşdıraq. Hər bir karta isə onun tərəflərindəki şəkillərə uyğun təpələri birləşdirən istiqamətlənməmiş tili uyğunlaşdıraq. Alınan qraf baş verə bilər ki, əlaqəli olmasın.

Əgər qrafın hər bir əlaqəlilik komponentində birdən çox olmayan tsikl varsa, məsələnin cavabı possible olacaqdır. Əlaqəlilik komponentlərini və onlardakı tsiklərin sayını kəsişməyən çoxluqlar sistemi vasitəsilə müəyyən etmək olar.

Misal

Dörd kartı nəzərdən keçirək. Kartların yuxarı çevrilmiş tərəflərini sarı rənglə işarə edək. Qrafın hər bir tilinə uyğun kartın yuxarıda yerləşən şəklini uyğunlaşdıraq.

İki əlaqəlilik komponenti olan halı nəzərdən keçirək:

Alqoritmin realizasiyası

Məlumatların emalı üçün massivlər təyin edək. $dsu$ massivi kəsişməyən çoxluqlar sistemi üçün istifadə olunur. Əgər $i$ çoxluğun nümayəndəsidirsə, onda has\_cycle[i] orada olan tsiklərin sayı haqqında məlumatı saxlayır:

• has\_cycle[i] = 0, tsikl yoxdur;

• has\_cycle[i] = 1, bir tsikl mövcuddur;

• has\_cycle[i] > 1, birdən çox tsikl mövcuddur;

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

Repr funksiyası $n$ təpəsini özündə saxlayan çoxluğun nümayəndəsini qaytarır.

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

Union funksiyası $x$ və $y$ təpələrini özündə saxlayan çoxluqları birləşdirir.

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

Əgər $x$ və $y$ təpələri artıq eyni əlaqəlilik komponentinə aiddirsə (onların nümayəndəsi eynidirsə) və eyni zamanda $(x,y)$ tili əlavə olunursa, onda daha bir tsikl əmələ gəlir. Bu halda həmin çoxluğun nümayəndəsinin tsikllərinin sayını artırırıq (x_1 — $x$ və $y$-in nümayəndəsidir):

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

Əgər $x$ və $y$ müxtəlif əlaqəlilik komponentlərinə aiddirsə, onda onların birləşdirilməsini yerinə yetiririk, bu zaman y_1 nümayəndəsi birləşdirilmiş çoxluğun nümayəndəsi olur. Bu halda kökü y_1 olan komponentin tsikllərinin sayına kökü x_1 olan komponentin tsikllərinin sayını əlavə edirik.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Kəsişməyən çoxluqlar sistemini ilkinləşdiririk.

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

Kəsişməyən çoxluqlar sistemini qururuq.

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

Birdən çox tsikl saxlayan ən azı bir əlaqəlilik komponentinin mövcud olub-olmadığını yoxlayırıq.

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

Cavabı çap edirik.

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