Yeganə topoloji sıralama#10652

Yeganə topoloji sıralama (Həll təhlili)

Biz Kahn alqoritmindən istifadə edirik. Yadda saxlayaq ki, o, giriş dərəcəsi sıfır olan təpələrin növbəsini saxlayır – bunlar məhz topoloji sıralamanın növbəti mövqeyinə yerləşdirilə bilən təpələrdir. Hər iterasiyada növbədən bir təpə çıxarılır və cavaba əlavə edilir, onun bütün qonşularının giriş dərəcəsi $1$ azaldılır. Giriş dərəcəsi sıfır olan təpələr növbəyə əlavə edilir.

Əsas müşahidə: topoloji sıralama o zaman və yalnız o zaman unikaldır ki, hər çıxarılmadan əvvəl növbədə dəqiq bir təpə olsun.

Mürəkkəblik. Hər təpə və hər tərəf bir dəfə emal olunur, buna görə işləmə vaxtı $O (n + m)$ O(n + m)-dir.

Nümunə

Test hallarından olan qraflar aşağıdakı kimidir:

Birinci nümunədə topoloji sıralama unikaldır:

$1, 2, 3$ .

İkinci nümunədə isə iki mümkün topoloji sıralama var:

$1, 2, 3$ ;
$1, 3, 2$ ;

Alqoritmin həyata keçirilməsi

Giriş qrafını qonşuluq siyahısı $g$ şəklində saxlayırıq. Təpələrin giriş dərəcələri $I n D e g r ee$ InDegree massivində saxlanılır. $q$ növbəsini elan edirik.

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

Giriş qrafını oxuyuruq. Hər $(a, b)$ tərəfi üçün $I n D e g r ee [b]$ InDegree[b]-ni $1$ artırırıq.

scanf("%d %d", &n, &m);
g.resize(n + 1);
InDegree.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  InDegree[b]++;
}

C++

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

for (i = 1; i < InDegree.size(); i++)
  if (!InDegree[i]) q.push_back(i);

Topoloji sıralama unikal olarsa, $f l a g = 1$ flag = 1 təyin edirik.

flag = 1;

$q$ növbəsi boş olmadığı müddətcə alqoritmi davam etdiririk.

while (!q.empty())
{

Əgər növbədə birdən çox təpə varsa, onda topoloji sıralama unikal deyil.

  if (q.size() > 1) flag = 0;

Növbədən cari $v$ təpəsini çıxarırıq.

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

$(v, t o)$ (v, to) tərəflərini qrafdan silirik. Hər belə tərəf üçün $t o$ təpəsinin giriş dərəcəsini azaldırıq. Əgər $t o$ təpəsinin giriş dərəcəsi sıfır olarsa, onu növbəyə əlavə edirik.

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

$f l a g$ dəyərindən asılı olaraq cavabı çap edirik.

if (flag == 1)
  printf("YES\n");
else
  printf("NO\n");