Qraf (Həll təhlili)

Leksikoqrafik ən kiçik topoloji sıralama prioritet növbəsi ilə Kan alqoritmi vasitəsilə qurulur: hər addımda bütün əlçatan təpələr (hələ yazılmamış təpələrdən daxil olan tili olmayan təpələr) arasından ən kiçik nömrəli təpə seçilir.

Əlavə edilmiş $u \to v$ u \to v tili $v$ təpəsini $u$ təpəsi yazılana qədər əlçatmaz edir. Deməli, til əlavə etməklə kiçik təpələri "gizlədə" və bununla da alqoritmi daha böyük nömrəli təpələri seçməyə məcbur edə bilərik. Hər gizlədilmiş təpə $k$ ehtiyatından bir tilə başa gəlir.

Acgöz ideya. Cavabı mövqe-mövqe qururuq. Leksikoqrafik müqayisə ilk fərqlənən mövqe ilə müəyyən olunur, ona görə də hər mövqedə mümkün olan ən böyük nömrəli təpəni yerləşdirməliyik — sonrakı mövqelərdəki heç bir qazanc cari mövqedəki itkini kompensasiya edə bilməz.

Cari addımda yazıla bilən təpələri iki çoxluğa bölək:

$A$ — əlçatan təpələr: onlara daxil olan bütün tillər artıq "silinib". Heç nə etməsək, Kan alqoritmi $A$ -dan ən kiçik təpəni seçəcək;
$B$ — təxirə salınmış təpələr. Bunlar əlçatan olmuş, lakin gizlətməyi qərara aldığımız təpələrdir. Hər belə təpə üçün ona daxil olan bir til əlavə etməyi öhdəmizə götürürük. Bu tilin başlanğıcını sonra seçəcəyik — bu, təxirə salınmış təpədən bilavasitə əvvəl yazılan təpə olacaq.

$A$ çoxluğu ən kiçik elementi yuxarıda olan prioritet növbəsində (min-yığın), $B$ çoxluğu isə ən böyük elementi yuxarıda olan prioritet növbəsində (max-yığın) saxlanılır.

Təpəni nə vaxt təxirə salmaq sərfəlidir. Tutaq ki, $x$ — $A$ -dakı ən kiçik təpədir. Ona toxunmasaq, cari mövqeyə $x$ yerləşəcək. $x$ -i təxirə salmağın (bir til xərcləməyin) iki halda mənası var:

$A$ -da ən azı iki təpə var. Onda $x$ təxirə salındıqdan sonra cari mövqeyə $A$ -dakı artan sırada növbəti, $x$ -dən böyük təpə yerləşəcək;
$A$ -da yalnız $x$ təpəsi var, lakin $B$ -də təxirə salınmış $y > x$ y > x təpəsi var. Onda $x$ təxirə salındıqdan sonra $A$ çoxluğu boş olur və cari mövqeyə ən böyük təxirə salınmış təpə — $x$ -dən böyük ədəd — yerləşəcək.

Bütün digər hallarda təxirə salmaq cari mövqedəki ədədi artırmır və til xərcləməyə ehtiyac yoxdur. Təpələri bir-bir, ən kiçikdən başlayaraq, sərfəli olduqca və $k$ ehtiyatı tükənməyincə təxirə salırıq.

Hansı təpəni yazmaq lazımdır. Təxirə salmadan sonra:

əgər $A$ boş deyilsə, $A$ -dan ən kiçik təpəni yazırıq — bunu leksikoqrafik ən kiçik sıralama qaydası tələb edir;
əgər $A$ boşdursa, $B$ -dən ən böyük təxirə salınmış $v$ təpəsini yazırıq və sonuncu yazılmış təpədən $v$ -yə til əlavə edirik. Məhz bu til $v$ təpəsini "gizlədirdi": indiyə qədər o əlçatmaz idi, indi isə onun yeni sələfi yazıldıqdan sonra o, yeganə əlçatan təpəyə çevrilir. Digər təxirə salınmış təpələr gizli qalır — onların tilləri sonra əlavə ediləcək.

Sonra, Kan alqoritmində olduğu kimi, yazılmış təpənin qonşularının giriş dərəcələrini azaldırıq; giriş dərəcəsi sıfıra bərabər olan təpələr $A$ -ya əlavə olunur.

Cavab niyə düzgündür. Hər təxirə salınmış təpə gec-tez $B$ -dən yazılır və həmin anda düz bir til əlavə olunur. Buna görə əlavə edilmiş tillərin sayı təxirə salmaların sayına bərabərdir və $k$ -dan çox deyil. Bütün əlavə edilmiş tillər əvvəl yazılmış təpədən sonra yazılmış təpəyə gedir, ona görə də tapılmış sıra yeni qrafın topoloji sıralamasıdır və heç bir dövr yaranmır.

Mürəkkəblik. Hər təpə $A$ -ya ən çox bir dəfə və $B$ -yə ən çox bir dəfə daxil olur, qrafın hər tilinə isə bir dəfə baxılır. Ümumi mürəkkəblik $O ((n + m) lo g n)$ O((n + m) \log n)-dir.

Məsələnin həlli alqoritmi

Kan alqoritmindən və iki prioritet növbəsindən istifadə edirik:

$A$ — əlçatan təpələri saxlayan min-yığın, yuxarısında ən kiçik nömrəli təpə yerləşir.
$B$ — təxirə salınmış təpələri saxlayan max-yığın, yuxarısında ən böyük nömrəli təpə yerləşir.

Aşağıdakı massivləri elan edək:

$in d e g [v]$ indeg[v] — $v$ təpəsinin hələ emal olunmamış daxil olan tillərinin sayı;
$an s$ — nəticə topoloji sıralama;
$e d g es$ — əlavə edilmiş tillərin siyahısı.

Addım 1. İnisializasiya

Hər təpənin giriş dərəcəsini hesablamaq.
Giriş dərəcəsi sıfır olan bütün təpələri $A$ -ya əlavə etmək.
$B$ -ni və $e d g es$ siyahısını boş olaraq inisializasiya etmək.

Addım 2. Cavabın qurulması

Bütün $n$ təpə emal olunmayana qədər:

1. Sərfəlidirsə, təpəni təxirə salmaq.

Əlavə edilmiş tillərin sayı $k$ -dan az olduqca, $A$ yığını boş olmadıqca və aşağıdakı şərtlərdən ən azı biri ödəndikcə:

$A$ -da ən azı iki təpə var;
$A$ -da yeganə $x$ təpəsi var, $B$ -də isə $y > x$ y > x olan $y$ təpəsi var.

$A$ -dan ən kiçik $x$ təpəsini çıxarıb $B$ -yə əlavə etmək. Bu təpə sonra emal olunacaq.

2. Növbəti təpəni seçmək.

Əgər $A$ boş deyilsə, ondan ən kiçik $v$ təpəsini çıxarmaq.
Əks halda $B$ -dən ən böyük $v$ təpəsini çıxarmaq. Əgər $an s$ boş deyilsə, $an s$ -dakı sonuncu təpədən $v$ -yə til əlavə etmək.

$v$ -ni $an s$ -ın sonuna əlavə etmək.

3. Qrafı yeniləmək.

Hər çıxan $v \to u$ v \to u tili üçün:

$in d e g [u]$ indeg[u]-nu bir vahid azaltmaq.
Əgər $in d e g [u]$ indeg[u] sıfıra bərabər olarsa, $u$ -nu $A$ -ya əlavə etmək.

Bütün təpələr $an s$ -a əlavə olunana qədər bu addımları təkrarlamaq.

Addım 3. Çıxış

$an s$ ardıcıllığını çap etmək.
Əlavə edilmiş tillərin sayını çap etmək.
Əlavə edilmiş tillərin özlərini çap etmək.

Nümunə

Şərtdəki nümunəyə baxaq: $n = 5$ n = 5, $k = 2$ k = 2, tillər $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. İlkin giriş dərəcələri: $1$ və $5$ təpələrinin giriş dərəcəsi $0$ , $2, 3, 4$ təpələrinin giriş dərəcəsi $1$ -dir. İlkin çoxluqlar: $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}.

Addım	Təxirə salınan	$A$	$B$	$k$	Götürülür	Til	Sıra
$1$	$1$ ( $A$ -da iki təpə)	${5}$	${1}$	$1$	$5$ , $A$ -dan	—	$5$
$2$	—	${}$	${1}$	$1$	$1$ , $B$ -dən	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ ( $A$ -da iki təpə: $3$ və $4$ )	${4}$	${3}$	$0$	$4$ , $A$ -dan	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$2$ , $A$ -dan	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$3$ , $B$ -dən	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Addımlara daha ətraflı baxaq.

Addım 1. $A = {1, 5}$ A = \{1, 5\} iki təpədən ibarətdir, ona görə də ən kiçiyini — $1$ -i təxirə salırıq. İndi $A = {5}$ A = \{5\} bir təpədən ibarətdir, $B$ -də isə $5$ -dən böyük təpə yoxdur, ona görə də təxirə salmanı dayandırırıq. $5$ -i yazırıq.
Addım 2. $A$ boşdur. Ən böyük təxirə salınmış $1$ təpəsini yazırıq və $5 \to 1$ 5 \to 1 tilini əlavə edirik. $1 \to 4$ 1 \to 4 və $1 \to 3$ 1 \to 3 tillərini silirik: $4$ və $3$ təpələri əlçatan olur, $A = {3, 4}$ A = \{3, 4\}.
Addım 3. $A$ -da iki təpə var — $3$ -ü təxirə salırıq və tillərin ehtiyatı tükənir ( $k = 0$ k = 0). $4$ -ü yazırıq, bundan sonra $4 \to 2$ 4 \to 2 tili silinir və $A = {2}$ A = \{2\}.
Addım 4. Daha təxirə salmaq mümkün deyil. $2$ -ni yazırıq.
Addım 5. $A$ boşdur. Təxirə salınmış $3$ təpəsini yazırıq və $2 \to 3$ 2 \to 3 tilini əlavə edirik.

$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 sırasını və əlavə edilmiş $5 \to 1$ 5 \to 1 və $2 \to 3$ 2 \to 3 tillərini alırıq. İlkin qraf (solda) və əlavə edilmiş tillərlə qraf (sağda, əlavə edilmiş tillər qırmızı rənglə göstərilib):

Əlavə tillər olmadan leksikoqrafik ən kiçik sıralama $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5-dir: $5$ təpəsi heç nə ilə əlaqəli deyil, lakin böyük nömrəsinə görə sonuncu seçilir. İki til əlavə edildikdən sonra $5$ təpəsi birinci olur və $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 sırası leksikoqrafik olaraq daha böyükdür.

Daha bir nümunəyə baxaq, burada əvvəlcə dörd təpə əlçatandır. Tutaq ki, $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4, qrafın tilləri isə $6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7$ 6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7-dir.

$1, 2, 4, 6$ 1, 2, 4, 6 təpələrinə heç bir til daxil olmur, ona görə də əvvəlcə $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}. Əlavə tillər olmadan leksikoqrafik ən kiçik sıralama $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8-dir.

İlkin qraf (solda) və tillər əlavə edildikdən sonrakı qraf (sağda, əlavə edilmiş tillər qırmızı rənglə göstərilib)

Addım	$A$ əvvəl	$B$ əvvəl	$k$	Təxirə salınan	Götürülür	Til
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$6$ , $A$ -dan	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$4$ , $B$ -dən	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$8$ , $A$ -dan	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$3$ , $B$ -dən	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$5$ , $A$ -dan	—
$6$	${}$	${2, 1}$	$0$	—	$2$ , $B$ -dən	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$1$ , $B$ -dən	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$7$ , $A$ -dan	—

Addımlara daha ətraflı baxaq.

Addım 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. $1$ təpəsini təxirə salırıq, çünki $A$ -da dörd təpə var, sonra $2$ -ni ( $A$ -da üç təpə), sonra $4$ -ü ( $A$ -da iki təpə). Ehtiyat $k = 1$ k = 1-ə qədər azalır. İndi $A = {6}$ A = \{6\} bir təpədən ibarətdir, ən böyük təxirə salınmış $4$ təpəsi isə $6$ -dan kiçikdir — daha təxirə salmaq sərfəli deyil. $6$ -nı yazırıq. $6 \to 3$ 6 \to 3 tili silinir və $A = {3}$ A = \{3\}.
Addım 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ -da bir təpə var, lakin $B$ -də $4 > 3$ 4 > 3 təpəsi var, ona görə də $3$ -ü də təxirə salırıq; ehtiyat tükənir, $k = 0$ k = 0. $A$ boşdur — ən böyük təxirə salınmış $4$ təpəsini yazırıq və $6 \to 4$ 6 \to 4 tilini əlavə edirik. $4 \to 8$ 4 \to 8 tili silinir və $A = {8}$ A = \{8\}.
Addım 3. Daha təxirə salmaq mümkün deyil. $8$ -i yazırıq, bundan sonra $A$ boşdur.
Addım 4. Ən böyük təxirə salınmış $3$ təpəsini yazırıq və $8 \to 3$ 8 \to 3 tilini əlavə edirik. $3 \to 5$ 3 \to 5 tili silinir və $A = {5}$ A = \{5\}.
Addım 5. $5$ -i yazırıq. $5 \to 7$ 5 \to 7 tili silinir, lakin $7$ təpəsinə hələ $1$ və $2$ -dən tillər daxil olur, ona görə də $A$ boşdur.
Addım 6. Təxirə salınmış $2$ təpəsini yazırıq və $5 \to 2$ 5 \to 2 tilini əlavə edirik. $2 \to 7$ 2 \to 7 tili silinir.
Addım 7. Təxirə salınmış $1$ təpəsini yazırıq və $2 \to 1$ 2 \to 1 tilini əlavə edirik. $1 \to 7$ 1 \to 7 tili silinir və $A = {7}$ A = \{7\}.
Addım 8. $7$ -ni yazırıq.

Cavab:

6 4 8 3 5 2 1 7
4
6 4
8 3
5 2
2 1

Bu nümunə alqoritmin bütün hallarını aydın göstərir. $1$ -ci addımda birdən üç təpə təxirə salınır — $A$ -da ən azı iki təpə olduqca. $2$ -ci addımda ikinci şərt işləyir: $A$ -da yalnız $3$ təpəsi var, lakin $B$ -də daha böyük $4$ təpəsi var, ona görə də $3$ də təxirə salınır. Təxirə salınmış təpələr $B$ -dən azalan sırada $(4, 3, 2, 1)$ (4, 3, 2, 1) çıxır və onların hər biri özündən əvvəl yazılmış təpədən düz bir til alır. Buna görə də düz təxirə salmaların sayı qədər til əlavə olunur — dörd.

Alqoritmin reallaşdırılması

Giriş verilənlərini oxuyuruq. Qrafı qururuq. Qonşuluq siyahıları $g$ -də, giriş dərəcələri $in d e g$ -də saxlanılır.

scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  indeg[v]++;
}

C++

İki prioritet növbəsi elan edək: $A$ — əlçatan təpələr, ən kiçik element yuxarıda (min-yığın); $B$ — təxirə salınmış təpələr, ən böyük element yuxarıda (max-yığın).

priority_queue<int, vector<int>, greater<int>> A; // əlçatan, min-yığın
priority_queue<int> B;                            // təxirə salınmış, max-yığın

Əvvəlcə giriş dərəcəsi sıfır olan bütün təpələr əlçatandır.

for (int v = 1; v <= n; v++)
  if (indeg[v] == 0) A.push(v);

$or d er$ massivində cavab — axtarılan topoloji sıralama toplanır, $a dd e d$ massivində isə əlavə edilmiş tillər saxlanılır.

vector<int> order;
order.reserve(n);
vector<pair<int, int>> added;

Dövrün hər iterasiyası cavaba bir təpə əlavə edir, bütün $n$ təpə yazılana qədər.

while ((int)order.size() < n)
{

Təpələri təxirə salırıq. Ehtiyatda til qaldıqca və $A$ çoxluğu boş olmadıqca, ən kiçik əlçatan $x$ təpəsinə baxırıq. Əgər $A$ -da ən azı daha bir təpə varsa və ya $B$ -də daha böyük nömrəli təxirə salınmış təpə varsa, onu təxirə salmaq sərfəlidir. Təxirə salınmış təpə $A$ -dan $B$ -yə köçürülür, $k$ ehtiyatı isə $1$ azalır. Əks halda təxirə salma dayanır.

  // sərfəli olduqca və til ehtiyatı qaldıqca təpələri təxirə salırıq
  while (k > 0 && !A.empty())
  {
    int x = A.top();
    if (A.size() >= 2 || (!B.empty() && B.top() > x))
    {
      A.pop();
      B.push(x);
      k--;
    }
    else break;
  }

C++

Cari mövqeyə yazılacaq $v$ təpəsini seçirik. Əgər $A$ boş deyilsə, bu, ən kiçik əlçatan təpədir. Əks halda ən böyük təxirə salınmış təpəni götürürük və sonuncu yazılmış $or d er . ba c k ()$ order.back() təpəsindən $v$ -yə til əlavə edirik.

  int v;
  if (!A.empty())
  {
    v = A.top();
    A.pop();
  }
  else
  {
    v = B.top();
    B.pop();
    added.push_back(make_pair(order.back(), v));
  }

C++

$v$ -ni cavaba əlavə edirik və Kan alqoritmində olduğu kimi onun qonşularının giriş dərəcələrini azaldırıq. Giriş dərəcəsi sıfıra bərabər olan təpələr əlçatan olur.

  order.push_back(v);
  for (int to : g[v])
    if (--indeg[to] == 0) A.push(to);
}

Tapılmış topoloji sıralamanı, əlavə edilmiş tillərin sayını və tillərin özlərini çap edirik.

for (int i = 0; i < n; i++)
  printf("%d ", order[i]);
printf("\n%d\n", added.size());
for (auto &e : added)
  printf("%d %d\n", e.first, e.second);