Grafo (Editoriale)

L'ordinamento topologico lessicograficamente minimo si costruisce con l'algoritmo di Kahn con una coda con priorità: a ogni passo, tra tutti i vertici disponibili (vertici in cui non entra alcun arco proveniente da vertici non ancora scritti), si sceglie il vertice con il numero più piccolo.

Un arco aggiunto $u \to v$ u \to v rende il vertice $v$ non disponibile finché non viene scritto il vertice $u$ . Quindi, aggiungendo archi, possiamo "nascondere" i vertici piccoli e costringere così l'algoritmo a scegliere vertici con numeri più grandi. Ogni vertice nascosto costa un arco del budget $k$ .

L'idea greedy. Costruiamo la risposta posizione per posizione. Il confronto lessicografico è deciso dalla prima posizione in cui le sequenze differiscono, quindi in ogni posizione dobbiamo mettere il vertice con il numero più grande possibile — nessun guadagno nelle posizioni successive può compensare una perdita in quella corrente.

Dividiamo i vertici che possono essere scritti al passo corrente in due insiemi:

$A$ — i vertici disponibili: tutti gli archi entranti in essi sono già stati "rimossi". Se non facciamo nulla, l'algoritmo di Kahn sceglie il vertice più piccolo di $A$ ;
$B$ — i vertici rinviati. Sono vertici che erano disponibili, ma che abbiamo deciso di nascondere. Per ciascuno di essi ci impegniamo ad aggiungere un arco entrante. L'origine di questo arco la sceglieremo più tardi — sarà il vertice scritto immediatamente prima di quello rinviato.

L'insieme $A$ è memorizzato in una coda con priorità con l'elemento più piccolo in cima (un min-heap), e l'insieme $B$ in una coda con priorità con l'elemento più grande in cima (un max-heap).

Quando conviene rinviare un vertice. Sia $x$ il vertice più piccolo di $A$ . Se lo lasciamo stare, nella posizione corrente verrà messo $x$ . Rinviare $x$ (spendendo un arco) ha senso in due casi:

$A$ contiene almeno due vertici. Allora, dopo aver rinviato $x$ , nella posizione corrente verrà messo il vertice successivo di $A$ in ordine crescente, che è maggiore di $x$ ;
$A$ contiene solo il vertice $x$ , ma $B$ contiene un vertice rinviato $y > x$ y > x. Allora, dopo aver rinviato $x$ , l'insieme $A$ diventa vuoto, e nella posizione corrente verrà messo il più grande vertice rinviato — un numero maggiore di $x$ .

In tutti gli altri casi il rinvio non aumenta il numero nella posizione corrente, e non c'è bisogno di spendere un arco. Rinviamo i vertici uno alla volta, a partire dal più piccolo, finché conviene e finché il budget $k$ non è esaurito.

Quale vertice scrivere. Dopo i rinvii:

se $A$ non è vuoto, scriviamo il vertice più piccolo di $A$ — questo è richiesto dalla regola dell'ordinamento lessicograficamente minimo;
se $A$ è vuoto, scriviamo il vertice rinviato più grande $v$ di $B$ e aggiungiamo un arco dall'ultimo vertice scritto a $v$ . È proprio questo arco che "nascondeva" il vertice $v$ : finora era non disponibile, e ora, quando il suo nuovo predecessore è stato scritto, diventa l'unico vertice disponibile. Gli altri vertici rinviati restano nascosti — i loro archi verranno aggiunti più tardi.

Poi, come al solito nell'algoritmo di Kahn, diminuiamo i gradi entranti dei vicini del vertice scritto; i vertici il cui grado entrante diventa zero vengono aggiunti ad $A$ .

Perché la risposta è corretta. Ogni vertice rinviato prima o poi viene scritto da $B$ , e in quel momento viene aggiunto esattamente un arco. Quindi il numero di archi aggiunti è uguale al numero di rinvii e non supera $k$ . Tutti gli archi aggiunti vanno da un vertice scritto prima a un vertice scritto dopo, perciò l'ordine trovato è un ordinamento topologico del nuovo grafo e non si formano cicli.

Complessità. Ogni vertice entra in $A$ al più una volta e in $B$ al più una volta, e ogni arco del grafo viene esaminato una volta. La complessità totale è $O ((n + m) lo g n)$ O((n + m) \log n).

Algoritmo di risoluzione del problema

Usiamo l'algoritmo di Kahn e due code con priorità:

$A$ — min-heap che memorizza i vertici disponibili, con il vertice di numero più piccolo in cima.
$B$ — max-heap che memorizza i vertici rinviati, con il vertice di numero più grande in cima.

Dichiariamo i seguenti array:

$in d e g [v]$ indeg[v] — il numero di archi entranti nel vertice $v$ non ancora elaborati;
$an s$ — l'ordinamento topologico risultante;
$e d g es$ — la lista degli archi aggiunti.

Passo 1. Inizializzazione

Calcolare il grado entrante di ogni vertice.
Aggiungere ad $A$ tutti i vertici con grado entrante zero.
Inizializzare $B$ e la lista $e d g es$ come vuoti.

Passo 2. Costruzione della risposta

Finché non sono stati elaborati tutti gli $n$ vertici:

1. Rinviare un vertice se conviene.

Finché il numero di archi aggiunti è minore di $k$ , lo heap $A$ non è vuoto e vale almeno una delle seguenti condizioni:

$A$ contiene almeno due vertici;
$A$ contiene un solo vertice $x$ , e $B$ contiene un vertice $y$ tale che $y > x$ y > x.

Estrarre il vertice più piccolo $x$ da $A$ e inserirlo in $B$ . Questo vertice verrà elaborato più tardi.

2. Scegliere il vertice successivo.

Se $A$ non è vuoto, estrarre da esso il vertice più piccolo $v$ .
Altrimenti, estrarre il vertice più grande $v$ da $B$ . Se $an s$ non è vuoto, aggiungere un arco dall'ultimo vertice di $an s$ a $v$ .

Aggiungere $v$ in fondo ad $an s$ .

3. Aggiornare il grafo.

Per ogni arco uscente $v \to u$ v \to u:

Diminuire $in d e g [u]$ indeg[u] di uno.
Se $in d e g [u]$ indeg[u] diventa zero, aggiungere $u$ ad $A$ .

Ripetere questi passi finché tutti i vertici non sono stati aggiunti ad $an s$ .

Passo 3. Output

Stampare la sequenza $an s$ .
Stampare il numero di archi aggiunti.
Stampare gli archi aggiunti.

Esempio

Consideriamo l'esempio del testo: $n = 5$ n = 5, $k = 2$ k = 2, archi $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. Gradi entranti iniziali: i vertici $1$ e $5$ hanno grado entrante $0$ , i vertici $2, 3, 4$ hanno grado entrante $1$ . Gli insiemi iniziali sono $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}.

Passo	Rinviati	$A$	$B$	$k$	Preso	Arco	Ordine
$1$	$1$ (due vertici in $A$ )	${5}$	${1}$	$1$	$5$ da $A$	—	$5$
$2$	—	${}$	${1}$	$1$	$1$ da $B$	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ (due vertici in $A$ : $3$ e $4$ )	${4}$	${3}$	$0$	$4$ da $A$	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$2$ da $A$	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$3$ da $B$	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Esaminiamo i passi più nel dettaglio.

Passo 1. $A = {1, 5}$ A = \{1, 5\} contiene due vertici, quindi rinviamo il più piccolo — $1$ . Ora $A = {5}$ A = \{5\} contiene un vertice, e $B$ non ha vertici maggiori di $5$ , quindi smettiamo di rinviare. Scriviamo $5$ .
Passo 2. $A$ è vuoto. Scriviamo il più grande vertice rinviato $1$ e aggiungiamo l'arco $5 \to 1$ 5 \to 1. Rimuoviamo gli archi $1 \to 4$ 1 \to 4 e $1 \to 3$ 1 \to 3: i vertici $4$ e $3$ diventano disponibili, $A = {3, 4}$ A = \{3, 4\}.
Passo 3. $A$ contiene due vertici — rinviamo $3$ , e il budget di archi è esaurito ( $k = 0$ k = 0). Scriviamo $4$ , dopodiché l'arco $4 \to 2$ 4 \to 2 viene rimosso e $A = {2}$ A = \{2\}.
Passo 4. Non sono possibili altri rinvii. Scriviamo $2$ .
Passo 5. $A$ è vuoto. Scriviamo il vertice rinviato $3$ e aggiungiamo l'arco $2 \to 3$ 2 \to 3.

Otteniamo l'ordine $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 e gli archi aggiunti $5 \to 1$ 5 \to 1 e $2 \to 3$ 2 \to 3. Il grafo originale (a sinistra) e il grafo con gli archi aggiunti (a destra, gli archi aggiunti sono in rosso):

Senza archi aggiunti l'ordinamento lessicograficamente minimo è $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5: il vertice $5$ non è collegato a nulla, ma a causa del suo numero grande viene scelto per ultimo. Dopo l'aggiunta di due archi, il vertice $5$ viene per primo, e l'ordine $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 è lessicograficamente maggiore.

Consideriamo un altro esempio, in cui all'inizio sono disponibili quattro vertici. Siano $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4, e siano gli archi del grafo $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.

Nei vertici $1, 2, 4, 6$ 1, 2, 4, 6 non entra alcun arco, quindi all'inizio $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}. Senza archi aggiunti l'ordinamento lessicograficamente minimo è $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8.

Il grafo originale (a sinistra) e il grafo dopo l'aggiunta degli archi (a destra, gli archi aggiunti sono in rosso)

Passo	$A$ prima	$B$ prima	$k$	Rinviati	Preso	Arco
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$6$ da $A$	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$4$ da $B$	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$8$ da $A$	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$3$ da $B$	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$5$ da $A$	—
$6$	${}$	${2, 1}$	$0$	—	$2$ da $B$	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$1$ da $B$	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$7$ da $A$	—

Esaminiamo i passi più nel dettaglio.

Passo 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. Rinviamo il vertice $1$ , poiché $A$ contiene quattro vertici, poi $2$ (tre vertici in $A$ ), poi $4$ (due vertici in $A$ ). Il budget scende a $k = 1$ k = 1. Ora $A = {6}$ A = \{6\} contiene un vertice, e il più grande vertice rinviato $4$ è minore di $6$ — rinviare ancora non conviene. Scriviamo $6$ . L'arco $6 \to 3$ 6 \to 3 viene rimosso, e $A = {3}$ A = \{3\}.
Passo 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ contiene un vertice, ma $B$ contiene il vertice $4 > 3$ 4 > 3, quindi rinviamo anche $3$ ; il budget è esaurito, $k = 0$ k = 0. $A$ è vuoto — scriviamo il più grande vertice rinviato $4$ e aggiungiamo l'arco $6 \to 4$ 6 \to 4. L'arco $4 \to 8$ 4 \to 8 viene rimosso, e $A = {8}$ A = \{8\}.
Passo 3. Non sono possibili altri rinvii. Scriviamo $8$ , dopodiché $A$ è vuoto.
Passo 4. Scriviamo il più grande vertice rinviato $3$ e aggiungiamo l'arco $8 \to 3$ 8 \to 3. L'arco $3 \to 5$ 3 \to 5 viene rimosso, e $A = {5}$ A = \{5\}.
Passo 5. Scriviamo $5$ . L'arco $5 \to 7$ 5 \to 7 viene rimosso, ma nel vertice $7$ entrano ancora archi da $1$ e $2$ , quindi $A$ è vuoto.
Passo 6. Scriviamo il vertice rinviato $2$ e aggiungiamo l'arco $5 \to 2$ 5 \to 2. L'arco $2 \to 7$ 2 \to 7 viene rimosso.
Passo 7. Scriviamo il vertice rinviato $1$ e aggiungiamo l'arco $2 \to 1$ 2 \to 1. L'arco $1 \to 7$ 1 \to 7 viene rimosso, e $A = {7}$ A = \{7\}.
Passo 8. Scriviamo $7$ .

La risposta:

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

Questo esempio mostra chiaramente tutti i casi dell'algoritmo. Al passo $1$ vengono rinviati tre vertici in una volta — finché $A$ contiene almeno due vertici. Al passo $2$ si applica la seconda condizione: $A$ contiene solo il vertice $3$ , ma $B$ contiene il vertice più grande $4$ , quindi anche $3$ viene rinviato. I vertici rinviati escono da $B$ in ordine decrescente $(4, 3, 2, 1)$ (4, 3, 2, 1), e ciascuno di essi riceve esattamente un arco dal vertice scritto prima di esso. Quindi vengono aggiunti esattamente tanti archi quanti sono stati i rinvii — quattro.

Implementazione dell'algoritmo

Leggiamo i dati di input. Costruiamo il grafo. Le liste di adiacenza sono memorizzate in $g$ , i gradi entranti in $in d e g$ .

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++

Dichiariamo due code con priorità: $A$ — i vertici disponibili, con l'elemento più piccolo in cima (un min-heap); $B$ — i vertici rinviati, con l'elemento più grande in cima (un max-heap).

priority_queue<int, vector<int>, greater<int>> A; // disponibili, min-heap
priority_queue<int> B;                            // rinviati, max-heap

Inizialmente sono disponibili tutti i vertici con grado entrante zero.

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

L'array $or d er$ accumula la risposta — l'ordinamento topologico richiesto, e l'array $a dd e d$ memorizza gli archi aggiunti.

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

Ogni iterazione del ciclo aggiunge un vertice alla risposta, finché non sono stati scritti tutti gli $n$ vertici.

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

Rinviamo i vertici. Finché nel budget restano archi e l'insieme $A$ non è vuoto, consideriamo il più piccolo vertice disponibile $x$ . Conviene rinviarlo se $A$ contiene almeno un altro vertice oppure se $B$ contiene un vertice rinviato con numero più grande. Un vertice rinviato viene spostato da $A$ a $B$ , e il budget $k$ diminuisce di $1$ . Altrimenti i rinvii si interrompono.

  // rinviamo i vertici finché conviene e restano archi
  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++

Scegliamo il vertice $v$ da scrivere nella posizione corrente. Se $A$ non è vuoto, è il più piccolo vertice disponibile. Altrimenti prendiamo il più grande vertice rinviato e aggiungiamo un arco dall'ultimo vertice scritto $or d er . ba c k ()$ order.back() a $v$ .

  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++

Aggiungiamo $v$ alla risposta e, come nell'algoritmo di Kahn, diminuiamo i gradi entranti dei suoi vicini. I vertici il cui grado entrante diventa zero diventano disponibili.

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

Stampiamo l'ordinamento topologico trovato, il numero di archi aggiunti e gli archi stessi.

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