Avengers (Editoriale)

Secondo l'enunciato del problema, è impossibile tornare alla città di partenza dopo aver percorso diverse strade, quindi il grafo delle strade è un grafo diretto aciclico.

Il compito è trovare tre vertici distinti tali che nessun cammino passi per tutti e tre, oppure segnalare che tali vertici non esistono.

Se n < 3, è impossibile scegliere tre città distinte, e la risposta è $-1$. D'ora in poi, supponiamo che n \ge 3.

Qualsiasi cammino in un grafo aciclico visita i vertici nell'ordine del loro ordinamento topologico. Pertanto, se un cammino contiene i vertici $x$ e $y$, allora uno di essi è raggiungibile dall'altro. Questo porta all'osservazione chiave: se esistono due vertici $x$ e $y$ tali che nessuno dei due è raggiungibile dall'altro, allora nessun cammino passa per entrambi. Di conseguenza, non esiste nemmeno un cammino che passi per la terna x, y, z, dove $z$ è un terzo vertice arbitrario.

Una tale coppia di vertici può essere trovata comodamente usando l'algoritmo di ordinamento topologico di Kahn. Inizialmente, tutti i vertici con grado entrante zero vengono inseriti nella coda. Successivamente, i vertici vengono estratti dalla coda uno a uno e rimossi dal grafo insieme ai loro archi uscenti; i vertici il cui grado entrante diventa zero in seguito a ciò vengono aggiunti alla coda.

Affermazione 1. Se in un certo momento la coda contiene simultaneamente due vertici $x$ e $y$, allora non esiste un cammino tra di loro.

Affermazione 2. Se a ogni passo dell'algoritmo la coda contiene esattamente un vertice, allora tutti i vertici del grafo giacciono su un unico cammino.

Quindi, l'algoritmo è il seguente: eseguire l'algoritmo di Kahn e controllare la dimensione della coda prima di ogni estrazione. Non appena essa contiene più di un vertice, prendere due qualsiasi di essi come $x$ e $y$, e un qualsiasi altro vertice del grafo come $z$. Se questo momento non si presenta mai, stampare $-1$.

Ogni vertice e ogni arco vengono elaborati al più una volta, quindi la complessità temporale dell'algoritmo è O(n + m), e l'utilizzo di memoria è O(n + m).

Esempio

I grafi degli esempi di test hanno la seguente struttura:

• Nel primo esempio, la coda contiene un singolo vertice a ogni passo: \{1\}, \{2\}, \{3\}. Il grafo contiene il cammino 1 \to 2 \to 3 che passa per tutti i vertici, quindi la risposta è $-1$.

• Nel secondo esempio, la coda contiene inizialmente il vertice $1$. Dopo la sua rimozione, i gradi entranti dei vertici $2$ e $3$ diventano zero, ed entrambi compaiono nella coda simultaneamente. Non esiste un cammino tra i vertici $2$ e $3$, quindi possiamo prendere x = 2, y = 3 e z = 1 come risposta.

Implementazione dell'algoritmo

Dichiariamo le strutture dati. Il grafo di input è rappresentato dalla lista di adiacenza $g$, e i gradi entranti dei vertici sono memorizzati nell'array InDegree.

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

Leggiamo i dati in input.

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

Per ogni arco $(a,b)$, incrementiamo InDegree[b] di $1$.

  InDegree[b]++;
}

Tutti i vertici con grado entrante zero vengono aggiunti alla coda $q$.

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

I tre vertici cercati sono memorizzati nelle variabili $x,y$ e $z$.

x = y = -1;

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

while (!q.empty())
{

Se la coda contiene più di un vertice nello stesso momento, significa che la soluzione è stata trovata.

  if (q.size() > 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

Estraiamo il vertice $v$ dalla coda — esso diventerà il vertice corrente nell'ordine topologico.

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

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

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

L'algoritmo di Kahn è completato. Se il valore di $x$ è ancora $-1$, significa che non esiste alcuna soluzione.

if (x == -1)
  printf("-1\n");
else
{

Se esiste una soluzione, scegliamo $z$ come il più piccolo vertice diverso da $x$ e $y$.

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}