Ordinazione topologica minima (Editoriale)

Una sequenza $a = (a_{1}, a_{2}, ..., a_{n})$ a = (a_1, a_2, ..., a_n) è lessicograficamente minore di una sequenza $b = (b_{1}, b_{2}, ..., b_{n})$ b = (b_1, b_2, ..., b_n) se, nella prima posizione $i$ in cui differiscono, vale $a_{i} < b_{i}$ a_i < b_i. Pertanto, per ottenere l'ordinamento topologico lessicograficamente più piccolo, al primo posto bisogna mettere il vertice più piccolo possibile, al secondo posto il più piccolo tra quelli possibili dato che il primo è già stato scelto, e così via.

Per risolvere il problema utilizzeremo l'algoritmo di Kahn. Per ogni vertice calcoliamo il suo grado entrante — il numero di archi entranti in esso. Un vertice può essere posto nella prossima posizione dell'ordinamento topologico se e solo se tutti i suoi predecessori sono già stati scritti, cioè il suo grado entrante attuale è pari a zero.

Nell'algoritmo classico di Kahn, i vertici con grado entrante nullo vengono memorizzati in una normale coda ed estratti in ordine arbitrario. Per ottenere la risposta lessicograficamente più piccola, sostituiamo la coda con una coda con priorità (oppure un insieme set), da cui ogni volta viene estratto il vertice con il numero più piccolo.

L'algoritmo si presenta nel modo seguente:

calcoliamo i gradi entranti di tutti i vertici;
inseriamo nella coda con priorità tutti i vertici con grado entrante nullo — sono proprio questi i vertici che possono iniziare l'ordinamento topologico;
finché la coda non è vuota, estraiamo da essa il vertice $v$ con il numero più piccolo e lo aggiungiamo alla risposta. Quindi, per ogni arco $v \to u$ v \to u, diminuiamo di $1$ il grado entrante del vertice $u$ . Se esso diventa pari a zero, aggiungiamo $u$ alla coda.

Rilevamento del ciclo. Se il grafo contiene un ciclo, allora nessuno dei vertici del ciclo otterrà mai grado entrante nullo e non finirà mai nella coda. Pertanto, se al termine dell'algoritmo nella risposta sono finiti meno di n vertici, l'ordinamento topologico non è possibile — restituiamo $- 1$ .

Complessità. Ogni vertice viene aggiunto alla coda con priorità ed estratto da essa esattamente una volta, ogni arco viene esaminato una sola volta. Il tempo di esecuzione è $O (n l o g n + m)$ O(n~log~n + m).

Esempio

Il grafo presentato nell'esempio ha il seguente aspetto:

Questo grafo ammette diverse varianti di ordinamento topologico. Ad esempio:

$1, 4, 6, 3, 2, 5$ 1, 4, 6, 3, 2, 5;
$4, 3, 6, 1, 2, 5$ 4, 3, 6, 1, 2, 5;
$3, 1, 4, 2, 6, 5$ 3, 1, 4, 2, 6, 5;

L'ordinamento topologico lessicograficamente più piccolo è

1, 3, 4, 2, 6, 5

1, 3, 4, 2, 6, 5

L'ordinamento topologico lessicograficamente più grande è

4, 6, 3, 1, 2, 5

4, 6, 3, 1, 2, 5

Implementazione dell'algoritmo — set

Memorizziamo il grafo in input sotto forma di lista di adiacenza $g$ . I gradi entranti dei vertici vengono memorizzati nell'array $I n D e g r ee$ InDegree. I vertici del grafo ordinati topologicamente vengono inseriti nell'array $O r d er$ .

vector<vector<int> > g;
vector<int> InDegree, Order;
set<int> minHeap;

Leggiamo il grafo in input.

scanf("%d %d", &n, &m);
g.resize(n + 1);
InDegree.resize(n + 1);

Calcoliamo i gradi entranti per tutti i vertici. Per ogni arco $(a, b)$ incrementiamo il valore del grado entrante del vertice $b$ .

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

Tutti i vertici con grado entrante nullo vengono aggiunti all'insieme $min H e a p$ .

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) minHeap.insert(i);

Continuiamo l'esecuzione dell'algoritmo di ordinamento topologico finché l'insieme $min H e a p$ non diventa vuoto.

while (!minHeap.empty())
{

Estraiamo da $min H e a p$ il vertice $v$ con il numero più piccolo e lo aggiungiamo alla fine dell'ordinamento topologico.

  v = *minHeap.begin();
  minHeap.erase(minHeap.begin());
  Order.push_back(v);

Rimuoviamo dal grafo tutti gli archi $(v, t o)$ (v, to) uscenti dal vertice $v$ . Per ciascuno di questi archi diminuiamo il grado entrante del vertice $t o$ . Se il grado entrante del vertice $t o$ diventa nullo, lo aggiungiamo all'insieme, da cui finirà nella lista dell'ordinamento topologico.

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

Se dopo l'esecuzione dell'algoritmo nell'array $O r d er$ non sono stati aggiunti tutti gli $n$ vertici, allora il grafo contiene un ciclo e l'ordinamento topologico non è possibile.

if (Order.size() < n)
  printf("-1");
else

Stampiamo i vertici del grafo nell'ordinamento topologico lessicograficamente più piccolo.

  for (i = 0; i < Order.size(); i++)
    printf("%d ", Order[i]);
printf("\n");

Implementazione dell'algoritmo — priority queue

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int> > g;
vector<int> InDegree, Order;
priority_queue<long long, vector<long long>, greater<long long> > pq;
int i, n, m, a, b, v, to;

int main(void)
{
  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]++;
  }

  for (i = 1; i < InDegree.size(); i++)
    if (InDegree[i] == 0) pq.push(i);

  while (!pq.empty())
  {
    v = pq.top(); pq.pop();
    Order.push_back(v);

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

  if (Order.size() < n)
    printf("-1");
  else
    for (int x : Order)
      printf("%d ", x);
  printf("\n");
  return 0;
}

Java

Implementazione Java — priority queue

import java.util.*;
import java.io.*;

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top;
  static int InDegree[];
  static int n, m, flag = 0;
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    InDegree = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
      InDegree[b]++;
    }

    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for(int i = 1; i <= n; i++)
      if (InDegree[i] == 0) pq.add(i);

    top = new ArrayList<Integer>();
    while (!pq.isEmpty())
    {
      int v = pq.poll();
      top.add(v);
      for (int to : g.get(v))
      {
        InDegree[to]--;
        if (InDegree[to] == 0) pq.add(to);
      }
    }

    if (top.size() < n)
      System.out.println("-1");
    else
    {
      for (int x : top) System.out.print(x + " ");
        System.out.println();
    }
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Java

Implementazione Python — priority queue

Importiamo le funzioni $h e a pp u s h$ heappush e $h e a pp o p$ dal modulo $h e a pq$ . $h e a pq$ — è una libreria integrata di Python, che fornisce un'implementazione di coda con priorità basata su heap.

from heapq import heappush, heappop

Leggiamo il numero di vertici $n$ e di archi $m$ nel grafo.

n, m = map(int, input().split())

Memorizziamo il grafo in input sotto forma di lista di adiacenza $g$ . I gradi entranti dei vertici vengono memorizzati nell'array $I n D e g r ee$ InDegree.

g = [[] for _ in range(n + 1)]
InDegree = [0] * (n + 1)

Leggiamo il grafo in input. Calcoliamo i gradi entranti per tutti i vertici. Per ogni arco $(a, b)$ incrementiamo il valore del grado entrante del vertice $b$ .

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)
  InDegree[b] += 1

Tutti i vertici con grado entrante nullo vengono aggiunti alla lista $min H e a p$ .

minHeap = []
for i in range(1, len(InDegree)):
  if InDegree[i] == 0:
    heappush(minHeap, i)

I vertici del grafo ordinati topologicamente vengono inseriti nell'array $O r d er$ .

Order = []

Continuiamo l'esecuzione dell'algoritmo di ordinamento topologico finché la lista $min H e a p$ non diventa vuota.

while minHeap:

Estraiamo da $min H e a p$ il vertice $v$ con il numero più piccolo e lo aggiungiamo alla fine dell'ordinamento topologico.

  v = heappop(minHeap)
  Order.append(v)

Rimuoviamo dal grafo tutti gli archi $(v, t o)$ (v, to) uscenti dal vertice $v$ . Per ciascuno di questi archi diminuiamo il grado entrante del vertice $t o$ . Se il grado entrante del vertice $t o$ diventa nullo, lo aggiungiamo alla coda, da cui finirà nella lista dell'ordinamento topologico.

  for to in g[v]:
    InDegree[to] -= 1
    if InDegree[to] == 0:
      heappush(minHeap, to)

Se dopo l'esecuzione dell'algoritmo nell'array $O r d er$ non sono stati aggiunti tutti gli $n$ vertici, allora il grafo contiene un ciclo e l'ordinamento topologico non è possibile.

if len(Order) < n:
  print(-1)

Stampiamo i vertici del grafo nell'ordinamento topologico lessicograficamente più piccolo.

else:
  print(*Order)