Ordinamento topologico unico#10652

Ordinamento topologico unico (Editoriale)

Utilizziamo l'algoritmo di Kahn. Ricordiamo che esso mantiene una coda di vertici con grado entrante zero – esattamente i vertici che possono essere posizionati nella prossima posizione dell'ordinamento topologico. Ad ogni iterazione, un vertice viene estratto dalla coda e aggiunto alla risposta, e i gradi entranti di tutti i suoi vicini vengono diminuiti di $1$ . I vertici il cui grado entrante diventa zero vengono aggiunti alla coda.

Osservazione chiave: l'ordinamento topologico è unico se e solo se la coda contiene esattamente un vertice prima di ogni estrazione.

Complessità. Ogni vertice e ogni arco vengono elaborati una sola volta, quindi il tempo di esecuzione è $O (n + m)$ O(n + m).

Esempio

I grafi dei casi di test sono i seguenti:

Nel primo esempio l'ordinamento topologico è unico:

$1, 2, 3$ .

Nel secondo esempio ci sono due possibili ordinamenti topologici:

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

Implementazione dell'algoritmo

Memorizziamo il grafo di input in una lista di adiacenza $g$ . I gradi entranti dei vertici sono memorizzati nell'array $I n D e g r ee$ InDegree. Dichiariamo la coda $q$ .

vector<vector<int> > g;
vector<int> InDegree;
deque<int> q;

Leggiamo il grafo di input. Per ogni arco $(a, b)$ incrementiamo $I n D e g r ee [b]$ InDegree[b] di $1$ .

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

Aggiungiamo alla coda $q$ tutti i vertici con grado entrante zero.

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

Impostiamo $f l a g = 1$ flag = 1 se l'ordinamento topologico è unico.

flag = 1;

Continuiamo l'algoritmo finché la coda $q$ non è vuota.

while (!q.empty())
{

Se la coda contiene più di un vertice, allora l'ordinamento topologico non è unico.

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

Estraiamo il vertice corrente $v$ dalla coda.

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

Rimuoviamo gli archi $(v, t o)$ (v, to) dal grafo. Per ciascuno di questi archi, diminuiamo il grado entrante del vertice $t o$ . Se il grado entrante del vertice $t o$ diventa zero, lo aggiungiamo alla coda.

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

A seconda del valore di $f l a g$ , stampiamo la risposta.

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