Graf (Editoryal)

Sözlük sırasına göre en küçük topolojik sıralama, öncelik kuyruklu Kahn algoritması ile oluşturulur: her adımda tüm erişilebilir düğümler (henüz yazılmamış düğümlerden gelen hiçbir kenarı olmayan düğümler) arasından en küçük numaralı düğüm seçilir.

Eklenen bir $u \to v$ u \to v kenarı, $u$ düğümü yazılana kadar $v$ düğümünü erişilemez yapar. Dolayısıyla kenar ekleyerek küçük düğümleri "gizleyebilir" ve böylece algoritmayı daha büyük numaralı düğümleri seçmeye zorlayabiliriz. Gizlenen her düğüm, $k$ bütçesinden bir kenara mal olur.

Açgözlü fikir. Cevabı pozisyon pozisyon oluştururuz. Sözlük sırasına göre karşılaştırma, ilk farklı pozisyon tarafından belirlenir; bu yüzden her pozisyona mümkün olan en büyük numaralı düğümü yerleştirmeliyiz — sonraki pozisyonlardaki hiçbir kazanç, mevcut pozisyondaki bir kaybı telafi edemez.

Mevcut adımda yazılabilecek düğümleri iki kümeye ayıralım:

$A$ — erişilebilir düğümler: bunlara giren tüm kenarlar zaten "kaldırılmıştır". Hiçbir şey yapmazsak, Kahn algoritması $A$ 'nın en küçük düğümünü seçer;
$B$ — ertelenmiş düğümler. Bunlar erişilebilir olan, ancak gizlemeye karar verdiğimiz düğümlerdir. Bu tür her düğüm için ona giren bir kenar eklemeyi taahhüt ederiz. Bu kenarın başlangıcını daha sonra seçeriz — bu, ertelenmiş düğümden hemen önce yazılan düğüm olacaktır.

$A$ kümesi, en küçük elemanı tepede olan bir öncelik kuyruğunda (min-heap), $B$ kümesi ise en büyük elemanı tepede olan bir öncelik kuyruğunda (max-heap) saklanır.

Bir düğümü ertelemek ne zaman kârlıdır. $x$ , $A$ 'daki en küçük düğüm olsun. Ona dokunmazsak, mevcut pozisyona $x$ yerleşir. $x$ 'i ertelemek (bir kenar harcamak) iki durumda anlamlıdır:

$A$ en az iki düğüm içeriyor. O zaman $x$ ertelendikten sonra mevcut pozisyona $A$ 'nın artan sıradaki bir sonraki düğümü yerleşir ve bu düğüm $x$ 'ten büyüktür;
$A$ yalnızca $x$ düğümünü içeriyor, ancak $B$ ertelenmiş bir $y > x$ y > x düğümü içeriyor. O zaman $x$ ertelendikten sonra $A$ kümesi boşalır ve mevcut pozisyona en büyük ertelenmiş düğüm — $x$ 'ten büyük bir sayı — yerleşir.

Diğer tüm durumlarda erteleme mevcut pozisyondaki sayıyı artırmaz ve kenar harcamaya gerek yoktur. Düğümleri, en küçüğünden başlayarak, kârlı olduğu sürece ve $k$ bütçesi tükenmediği sürece birer birer erteleriz.

Hangi düğüm yazılmalı. Ertelemeden sonra:

$A$ boş değilse, $A$ 'nın en küçük düğümünü yazarız — bu, sözlük sırasına göre en küçük sıralama kuralının gereğidir;
$A$ boşsa, $B$ 'deki en büyük ertelenmiş $v$ düğümünü yazar ve son yazılan düğümden $v$ 'ye bir kenar ekleriz. $v$ düğümünü "gizleyen" tam olarak bu kenardır: şimdiye kadar erişilemezdi, şimdi ise yeni öncülü yazıldığında tek erişilebilir düğüm hâline gelir. Diğer ertelenmiş düğümler gizli kalır — onların kenarları daha sonra eklenecektir.

Ardından, Kahn algoritmasında her zamanki gibi, yazılan düğümün komşularının giriş derecelerini azaltırız; giriş derecesi sıfır olan düğümler $A$ 'ya eklenir.

Cevap neden doğrudur. Her ertelenmiş düğüm er ya da geç $B$ 'den yazılır ve o anda tam olarak bir kenar eklenir. Bu nedenle eklenen kenar sayısı erteleme sayısına eşittir ve $k$ 'yı aşmaz. Eklenen tüm kenarlar daha önce yazılmış bir düğümden daha sonra yazılmış bir düğüme gider; dolayısıyla bulunan sıra yeni grafın bir topolojik sıralamasıdır ve döngü oluşmaz.

Karmaşıklık. Her düğüm $A$ 'ya en fazla bir kez ve $B$ 'ye en fazla bir kez girer, grafın her kenarı bir kez incelenir. Toplam karmaşıklık $O ((n + m) lo g n)$ O((n + m) \log n)'dir.

Problemin çözüm algoritması

Kahn algoritmasını ve iki öncelik kuyruğunu kullanırız:

$A$ — erişilebilir düğümleri saklayan min-heap, tepesinde en küçük numaralı düğüm bulunur.
$B$ — ertelenmiş düğümleri saklayan max-heap, tepesinde en büyük numaralı düğüm bulunur.

Aşağıdaki dizileri tanımlayalım:

$in d e g [v]$ indeg[v] — $v$ düğümünün henüz işlenmemiş gelen kenarlarının sayısı;
$an s$ — elde edilen topolojik sıralama;
$e d g es$ — eklenen kenarların listesi.

Adım 1. Başlatma

Her düğümün giriş derecesini hesapla.
Giriş derecesi sıfır olan tüm düğümleri $A$ 'ya ekle.
$B$ 'yi ve $e d g es$ listesini boş olarak başlat.

Adım 2. Cevabın oluşturulması

Tüm $n$ düğüm işlenmediği sürece:

1. Kârlıysa bir düğümü ertele.

Eklenen kenar sayısı $k$ 'dan küçük olduğu, $A$ yığını boş olmadığı ve aşağıdaki koşullardan en az biri sağlandığı sürece:

$A$ en az iki düğüm içeriyor;
$A$ tek bir $x$ düğümü içeriyor ve $B$ , $y > x$ y > x olacak şekilde bir $y$ düğümü içeriyor.

$A$ 'dan en küçük $x$ düğümünü çıkar ve $B$ 'ye ekle. Bu düğüm daha sonra işlenecektir.

2. Sonraki düğümü seç.

$A$ boş değilse, ondan en küçük $v$ düğümünü çıkar.
Aksi hâlde $B$ 'den en büyük $v$ düğümünü çıkar. $an s$ boş değilse, $an s$ 'taki son düğümden $v$ 'ye bir kenar ekle.

$v$ 'yi $an s$ 'ın sonuna ekle.

3. Grafı güncelle.

Her çıkan $v \to u$ v \to u kenarı için:

$in d e g [u]$ indeg[u]'yu bir azalt.
$in d e g [u]$ indeg[u] sıfır olursa, $u$ 'yu $A$ 'ya ekle.

Tüm düğümler $an s$ 'a eklenene kadar bu adımları tekrarla.

Adım 3. Çıktı

$an s$ dizisini yazdır.
Eklenen kenarların sayısını yazdır.
Eklenen kenarların kendilerini yazdır.

Örnek

Problem metnindeki örneği ele alalım: $n = 5$ n = 5, $k = 2$ k = 2, kenarlar $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. Başlangıç giriş dereceleri: $1$ ve $5$ düğümlerinin giriş derecesi $0$ , $2, 3, 4$ düğümlerinin giriş derecesi $1$ 'dir. Başlangıç kümeleri $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}'dir.

Adım	Ertelenen	$A$	$B$	$k$	Alınan	Kenar	Sıra
$1$	$1$ ( $A$ 'da iki düğüm)	${5}$	${1}$	$1$	$A$ 'dan $5$	—	$5$
$2$	—	${}$	${1}$	$1$	$B$ 'den $1$	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ ( $A$ 'da iki düğüm: $3$ ve $4$ )	${4}$	${3}$	$0$	$A$ 'dan $4$	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$A$ 'dan $2$	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$B$ 'den $3$	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Adımları daha ayrıntılı inceleyelim.

Adım 1. $A = {1, 5}$ A = \{1, 5\} iki düğüm içerir, bu yüzden en küçüğünü — $1$ 'i — erteleriz. Şimdi $A = {5}$ A = \{5\} tek bir düğüm içerir ve $B$ 'de $5$ 'ten büyük düğüm yoktur, bu yüzden ertelemeyi durdururuz. $5$ 'i yazarız.
Adım 2. $A$ boştur. En büyük ertelenmiş düğüm olan $1$ 'i yazar ve $5 \to 1$ 5 \to 1 kenarını ekleriz. $1 \to 4$ 1 \to 4 ve $1 \to 3$ 1 \to 3 kenarlarını kaldırırız: $4$ ve $3$ düğümleri erişilebilir hâle gelir, $A = {3, 4}$ A = \{3, 4\}.
Adım 3. $A$ iki düğüm içerir — $3$ 'ü erteleriz ve kenar bütçesi tükenir ( $k = 0$ k = 0). $4$ 'ü yazarız, ardından $4 \to 2$ 4 \to 2 kenarı kaldırılır ve $A = {2}$ A = \{2\}.
Adım 4. Başka erteleme mümkün değildir. $2$ 'yi yazarız.
Adım 5. $A$ boştur. Ertelenmiş $3$ düğümünü yazar ve $2 \to 3$ 2 \to 3 kenarını ekleriz.

$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 sırasını ve eklenen $5 \to 1$ 5 \to 1 ve $2 \to 3$ 2 \to 3 kenarlarını elde ederiz. Orijinal graf (solda) ve eklenen kenarlarla graf (sağda, eklenen kenarlar kırmızı ile gösterilmiştir):

Kenar eklenmeden sözlük sırasına göre en küçük sıralama $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5'tir: $5$ düğümü hiçbir şeye bağlı değildir, ancak büyük numarası nedeniyle en son seçilir. İki kenar eklendikten sonra $5$ düğümü ilk sıraya geçer ve $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 sırası sözlük sırasına göre daha büyüktür.

Bir örnek daha ele alalım; bu örnekte başlangıçta dört düğüm erişilebilirdir. $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4 olsun ve grafın kenarları $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 olsun.

$1, 2, 4, 6$ 1, 2, 4, 6 düğümlerine hiçbir kenar girmez, bu yüzden başlangıçta $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}'dir. Kenar eklenmeden sözlük sırasına göre en küçük sıralama $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8'dir.

Orijinal graf (solda) ve kenarlar eklendikten sonraki graf (sağda, eklenen kenarlar kırmızı ile gösterilmiştir)

Adım	$A$ önce	$B$ önce	$k$	Ertelenen	Alınan	Kenar
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$A$ 'dan $6$	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$B$ 'den $4$	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$A$ 'dan $8$	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$B$ 'den $3$	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$A$ 'dan $5$	—
$6$	${}$	${2, 1}$	$0$	—	$B$ 'den $2$	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$B$ 'den $1$	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$A$ 'dan $7$	—

Adımları daha ayrıntılı inceleyelim.

Adım 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. $A$ dört düğüm içerdiği için $1$ düğümünü, ardından $2$ 'yi ( $A$ 'da üç düğüm), sonra $4$ 'ü ( $A$ 'da iki düğüm) erteleriz. Bütçe $k = 1$ k = 1'e düşer. Şimdi $A = {6}$ A = \{6\} tek bir düğüm içerir ve en büyük ertelenmiş düğüm $4$ , $6$ 'dan küçüktür — ertelemeye devam etmek kârlı değildir. $6$ 'yı yazarız. $6 \to 3$ 6 \to 3 kenarı kaldırılır ve $A = {3}$ A = \{3\}.
Adım 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ tek bir düğüm içerir, ancak $B$ , $4 > 3$ 4 > 3 düğümünü içerir, bu yüzden $3$ 'ü de erteleriz; bütçe tükenir, $k = 0$ k = 0. $A$ boştur — en büyük ertelenmiş düğüm olan $4$ 'ü yazar ve $6 \to 4$ 6 \to 4 kenarını ekleriz. $4 \to 8$ 4 \to 8 kenarı kaldırılır ve $A = {8}$ A = \{8\}.
Adım 3. Başka erteleme mümkün değildir. $8$ 'i yazarız, ardından $A$ boştur.
Adım 4. En büyük ertelenmiş düğüm olan $3$ 'ü yazar ve $8 \to 3$ 8 \to 3 kenarını ekleriz. $3 \to 5$ 3 \to 5 kenarı kaldırılır ve $A = {5}$ A = \{5\}.
Adım 5. $5$ 'i yazarız. $5 \to 7$ 5 \to 7 kenarı kaldırılır, ancak $7$ düğümüne hâlâ $1$ ve $2$ 'den kenarlar girer, bu yüzden $A$ boştur.
Adım 6. Ertelenmiş $2$ düğümünü yazar ve $5 \to 2$ 5 \to 2 kenarını ekleriz. $2 \to 7$ 2 \to 7 kenarı kaldırılır.
Adım 7. Ertelenmiş $1$ düğümünü yazar ve $2 \to 1$ 2 \to 1 kenarını ekleriz. $1 \to 7$ 1 \to 7 kenarı kaldırılır ve $A = {7}$ A = \{7\}.
Adım 8. $7$ 'yi yazarız.

Cevap:

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

Bu örnek algoritmanın tüm durumlarını açıkça gösterir. $1$ . adımda tek seferde üç düğüm ertelenir — $A$ en az iki düğüm içerdiği sürece. $2$ . adımda ikinci koşul geçerli olur: $A$ yalnızca $3$ düğümünü içerir, ancak $B$ daha büyük olan $4$ düğümünü içerir, bu yüzden $3$ de ertelenir. Ertelenmiş düğümler $B$ 'den azalan sırada $(4, 3, 2, 1)$ (4, 3, 2, 1) çıkar ve her biri kendisinden önce yazılan düğümden tam olarak bir kenar alır. Bu nedenle tam olarak erteleme sayısı kadar kenar eklenir — dört.

Algoritmanın gerçekleştirilmesi

Giriş verilerini okuyalım. Grafı oluşturalım. Komşuluk listeleri $g$ 'de, giriş dereceleri $in d e g$ 'de saklanı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 öncelik kuyruğu tanımlayalım: $A$ — erişilebilir düğümler, en küçük eleman tepede (min-heap); $B$ — ertelenmiş düğümler, en büyük eleman tepede (max-heap).

priority_queue<int, vector<int>, greater<int>> A; // erisilebilir, min-heap
priority_queue<int> B;                            // ertelenmis, max-heap

Başlangıçta giriş derecesi sıfır olan tüm düğümler erişilebilirdir.

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

$or d er$ dizisi cevabı — aranan topolojik sıralamayı — biriktirir, $a dd e d$ dizisi ise eklenen kenarları saklar.

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

Döngünün her iterasyonu, tüm $n$ düğüm yazılana kadar cevaba bir düğüm ekler.

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

Düğümleri erteleriz. Bütçede kenar kaldığı ve $A$ kümesi boş olmadığı sürece, en küçük erişilebilir $x$ düğümünü ele alırız. $A$ en az bir düğüm daha içeriyorsa veya $B$ daha büyük numaralı bir ertelenmiş düğüm içeriyorsa onu ertelemek kârlıdır. Ertelenen düğüm $A$ 'dan $B$ 'ye taşınır ve $k$ bütçesi $1$ azalır. Aksi hâlde erteleme durur.

  // karli oldugu ve kenar kaldigi surece dugumleri erteliyoruz
  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++

Mevcut pozisyona yazılacak $v$ düğümünü seçeriz. $A$ boş değilse, bu en küçük erişilebilir düğümdür. Aksi hâlde en büyük ertelenmiş düğümü alır ve son yazılan $or d er . ba c k ()$ order.back() düğümünden $v$ 'ye bir kenar ekleriz.

  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$ 'yi cevaba ekleriz ve Kahn algoritmasında olduğu gibi komşularının giriş derecelerini azaltırız. Giriş derecesi sıfır olan düğümler erişilebilir hâle gelir.

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

Bulunan topolojik sıralamayı, eklenen kenarların sayısını ve kenarların kendilerini yazdırırız.

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);