Avengers (Həll təhlili)

Məsələnin şərtinə əsasən, bir neçə yol boyunca hərəkət etdikdən sonra başlanğıc şəhərə qayıtmaq mümkün deyil, buna görə də yol qrafı istiqamətləndirilmiş asiklik qrafdır (DAG).

Tapşırıq ondan ibarətdir ki, elə üç fərqli təpə tapılsın ki, heç bir yol onların hamısından keçməsin, və ya belə təpələrin mövcud olmadığını bildirsin.

Əgər n \u003c 3 olarsa, üç fərqli şəhər seçmək mümkün deyil və cavab $-1$-dir. Bundan sonra n \ge 3 olduğunu qəbul edirik.

Asiklik qrafda istənilən yol təpələri onların topoloji sıralanma ardıcıllığında ziyarət edir. Buna görə də, əgər yol $x$ və $y$ təpələrini ehtiva edirsə, onda onlardan biri digərindən əlçatandır. Bu əsas müşahidəyə gətirib çıxarır: əgər elə $x$ və $y$ təpələri mövcuddursa ki, onlardan heç biri digərindən əlçatan deyilsə, onda heç bir yol onların hər ikisindən keçmir. Nəticədə, x, y, z üçlüyündən də heç bir yol keçmir, burada $z$ ixtiyari üçüncü təpədir.

Belə bir cüt təpəni Kana (Kahn) topoloji sıralama alqoritmindən istifadə edərək rahatlıqla tapmaq olar. Əvvəlcə giriş dərəcəsi sıfır olan bütün təpələr növbəyə yerləşdirilir. Sonra növbədən təpələr bir-bir çıxarılır və onlar çıxan kənarları ilə birlikdə qrafdan silinir; nəticədə giriş dərəcəsi sıfır olan təpələr növbəyə əlavə edilir.

İddia 1. Əgər alqoritmin hər hansı anında növbədə eyni zamanda $x$ və $y$ təpələri varsa, onda onlar arasında yol yoxdur.

İddia 2. Əgər alqoritmin hər addımında növbədə dəqiq bir təpə varsa, onda qrafın bütün təpələri tək bir yol üzərində yerləşir.

Beləliklə, alqoritm aşağıdakı kimidir: Kana alqoritmini işə salın və hər çıxarmadan əvvəl növbənin ölçüsünü yoxlayın. Növbənin ölçüsü birdən çox olan ilk anda, onlardan istənilən ikisini $x$ və $y$ kimi götürün, qrafın istənilən digər təpəsini isə $z$ kimi götürün. Əgər bu an heç vaxt baş vermirsə, $-1$ çap edin.

Hər təpə və hər kənar ən çoxu bir dəfə işlənir, buna görə də alqoritmin vaxt mürəkkəbliyi O(n + m)-dir, yaddaş istifadəsi isə O(n + m)-dir.

Nümunə

Test nümunələrindəki qraflar aşağıdakı quruluşa malikdir:

• Birinci nümunədə növbə hər addımda tək bir təpə ehtiva edir: \{1\}, \{2\}, \{3\}. Qraf bütün təpələrdən keçən 1 \to 2 \to 3 yolunu ehtiva edir, buna görə də cavab $-1$-dir.

• İkinci nümunədə növbə ilkin olaraq $1$ təpəsini ehtiva edir. O çıxarıldıqdan sonra $2$ və $3$ təpələrinin giriş dərəcələri sıfır olur və onların hər ikisi eyni zamanda növbədə görünür. $2$ və $3$ təpələri arasında yol yoxdur, buna görə də cavab olaraq x = 2, y = 3 və z = 1 götürə bilərik.

Alqoritmin tətbiqi

Məlumat strukturlarını elan edin. Giriş qrafı qonşuluq siyahısı $g$ ilə təmsil olunur, təpələrin giriş dərəcələri isə InDegree massivində saxlanılır.

vector\u003cvector\u003cint\u003e \u003e g;
vector\u003cint\u003e InDegree;
deque\u003cint\u003e q;

Giriş məlumatlarını oxuyun.

scanf("%d %d", \u0026n, \u0026m);
g.resize(n + 1);
InDegree.resize(n + 1);
for (i = 0; i \u003c m; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);

Hər $(a,b)$ kənarı üçün InDegree[b] dəyərini $1$ artırın.

  InDegree[b]++;
}

Giriş dərəcəsi sıfır olan bütün təpələr $q$ növbəsinə əlavə edilir.

for (i = 1; i \u003c InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

Axtarılan üç təpə $x,y$ və $z$ dəyişənlərində saxlanılır.

x = y = -1;

$q$ növbəsi boş olmadığı müddətcə alqoritmi icra etməyə davam edin.

while (!q.empty())
{

Əgər növbə eyni anda birdən çox təpə ehtiva edirsə, bu o deməkdir ki, həll tapılıb.

  if (q.size() \u003e 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

$v$ təpəsini növbədən çıxarın — o, topoloji sıralamada cari təpə olacaq.

  v = q.front(); q.pop_front();

Qrafdan (v, to) formasındakı bütün kənarları silin. Hər belə kənar üçün $to$ təpəsinin giriş dərəcəsini azaldın. Əgər $to$-nun giriş dərəcəsi sıfır olarsa, onu növbəyə əlavə edin.

  for (int to : g[v])
  {
    InDegree[to]--;
    if (InDegree[to] == 0) q.push_back(to);
  }
}

Kana alqoritmi tamamlandı. Əgər $x$-in dəyəri hələ də $-1$-dirsə, bu o deməkdir ki, həll mövcud deyil.

if (x == -1)
  printf("-1\n");
else
{

Əgər həll mövcuddursa, $z$-ni $x$ və $y$-dən fərqli ən kiçik təpə kimi seçin.

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}