Metropolitana di Baku#11865

Metropolitana di Baku (Editoriale)

Lo schema della metropolitana è rappresentato da un grafo non orientato connesso con $n$ vertici e $n$ archi. Un grafo connesso su $n$ vertici, contenente esattamente $n - 1$ n - 1 archi, è un albero. Aggiungendo un ulteriore arco a un albero si crea esattamente un ciclo. Pertanto, il grafo descritto nella condizione è costituito da un unico ciclo (la linea circolare), ai cui vertici sono appesi degli alberi (eventualmente vuoti).

Per ogni vertice occorre trovare la lunghezza del cammino più breve verso il vertice più vicino del ciclo. Per i vertici del ciclo la risposta è pari a $0$ . Il problema si risolve in due fasi.

Fase 1. Individuazione del ciclo: rimozione sequenziale delle foglie

Calcoliamo i gradi di tutti i vertici. Inseriamo in una coda tutti i vertici di grado $1$ , cioè le foglie. Finché la coda non è vuota, estraiamo da essa un vertice $v$ e lo contrassegniamo come rimosso. Successivamente diminuiamo di $1$ il grado di ogni suo vicino non ancora rimosso. Se il grado di un vicino diventa pari a $1$ , allora esso stesso si è trasformato in una foglia, e lo aggiungiamo alla coda.

Al termine del processo rimarranno non rimossi solo i vertici del ciclo. Questo segue da due osservazioni:

Un vertice del ciclo non diventerà mai una foglia. Esso ha sempre due vicini lungo il ciclo, che a loro volta non vengono rimossi. Rigorosamente, ciò si dimostra per induzione sui passi del processo.
Ogni vertice di un albero pendente verrà rimosso. La rimozione delle foglie "rode" l'albero dal basso verso l'alto, dalle foglie fino al punto di attacco al ciclo. Questa procedura è analoga all'ordinamento topologico secondo l'algoritmo di Kahn, applicato però a un grafo non orientato.

Fase 2. Ricerca in ampiezza multi-sorgente

Poniamo $d [v] = 0$ d[v] = 0 per tutti i vertici del ciclo e $d [v] = -1$ d[v] = –1 (non visitato) per gli altri. Inseriamo tutti i vertici del ciclo nella coda contemporaneamente e avviamo da essi una ricerca in ampiezza. Quando un vertice $u$ viene estratto dalla coda, ogni suo vicino non visitato $w$ riceve il valore $d [w] = d [u] + 1$ d[w] = d[u] + 1 e viene aggiunto alla coda.

La ricerca in ampiezza da un insieme di sorgenti elabora i vertici in ordine non decrescente di distanza da tale insieme. Pertanto $d [v]$ è uguale al numero minimo di passaggi da $v$ alla linea circolare. Poiché tutto ciò che si trova al di fuori del ciclo è un albero, il percorso da ogni stazione fino all'anello è in realtà unico.

Finché nel grafo ci sono vertici di grado $1$ , li rimuoviamo.
Quando tali vertici non ci saranno più, nel grafo rimarranno solo i vertici che formano il ciclo.

Questo processo ricorda un ordinamento topologico inverso: rimuoviamo sequenzialmente le foglie finché non rimangono solo i vertici "interni" — sono proprio questi a costituire il ciclo.

Successivamente avviamo una ricerca in ampiezza simultaneamente da tutti i vertici appartenenti al ciclo. In questo modo determiniamo, per ogni vertice rimanente, il numero minimo di passi (passaggi) fino al vertice più vicino dell'anello.

Esempio

Nel primo esempio tutti i vertici fanno parte di un unico ciclo, pertanto la distanza per ciascuno di essi è pari a $0$ .

Nel secondo esempio il ciclo è formato dai vertici $2, 3$ e $5$ , mentre gli altri vertici si trovano a una certa distanza da esso.

Implementazione dell'algoritmo

Dichiariamo la lista di adiacenza del grafo $g$ , nonché gli array ausiliari:

$u se d$ — indicatore di rimozione del vertice: $u se d [v] = 1$ used[v] = 1 se il vertice $v$ è già stato rimosso come foglia, e $u se d [v] = 0$ used[v] = 0 se rimane ancora nel grafo. Al termine della prima fase, i valori nulli rimarranno solo per i vertici del ciclo;
$d i s t$ — array delle distanze: $d i s t [v]$ dist[v] è uguale al numero di passaggi dal vertice $v$ al vertice più vicino del ciclo (il valore $-1$ indica che il vertice non è ancora stato visitato);
$d e g$ — gradi correnti dei vertici: $d e g [v]$ deg[v] è uguale al numero di vicini del vertice $v$ che non sono ancora stati rimossi.

La coda $q$ viene utilizzata in entrambe le fasi dell'algoritmo: prima per la rimozione sequenziale delle foglie, poi per la ricerca in ampiezza multi-sorgente.

vector<vector<int> > g;
vector<int> used, dist, deg;
queue<int> q;

Leggiamo i dati di input. Costruiamo il grafo.

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

C++

Calcoliamo i gradi iniziali dei vertici: il grado del vertice $i$ è uguale alla dimensione della sua lista di adiacenza $g [i]$ . Tutte le foglie, cioè i vertici di grado $1$ , le inseriamo nella coda $q$ e le contrassegniamo subito come rimosse $(u se d [i] = 1)$ (used[i] = 1).

used.resize(n + 1, 0);
deg.resize(n + 1, 0);
for (i = 1; i <= n; i++)
{
  deg[i] = g[i].size();
  if (deg[i] == 1)
  {
    q.push(i);
    used[i] = 1;
  }
}

C++

Rimuoviamo sequenzialmente le foglie. Esternamente questo ciclo assomiglia a una ricerca in ampiezza, tuttavia un vertice entra nella coda non al primo incontro, ma solo quando esso stesso diventa una foglia. Estraiamo dalla coda il vertice $v$ e scorriamo i suoi vicini $t o$ . I vicini già contrassegnati come rimossi vengono saltati. Per ogni vicino non ancora rimosso diminuiamo il grado di $1$ , poiché l'arco $(v, t o)$ (v, to) scompare dal grafo insieme al vertice $v$ .

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (used[to] == 0)
    {
      deg[to]--;

C++

Se dopo la diminuzione il grado del vertice to diventa uguale a $1$ , significa che gli è rimasto un unico vicino non rimosso, cioè esso stesso si è trasformato in una foglia. Lo inseriamo nella coda e lo contrassegniamo come rimosso. I vertici del ciclo non raggiungono mai il grado $1$ , pertanto il processo si arresta sulla linea circolare.

      if (deg[to] == 1)
      {
        q.push(to);
        used[to] = 1;
      }
    }
}

C++

A questo punto l'uguaglianza $u se d [i] = 0$ used[i] = 0 vale se e solo se il vertice $i$ appartiene al ciclo.

Inizializziamo l'array $d i s t$ con il valore $-1$ (tutti i vertici non visitati). La coda a questo punto è già vuota, ma l'assegnazione di una coda vuota la reimposta esplicitamente prima del secondo attraversamento. Successivamente inseriamo ogni vertice del ciclo nella coda e poniamo per esso $d i s t [i] = 0$ dist[i] = 0 — tutti i vertici della linea circolare diventano contemporaneamente sorgenti della ricerca in ampiezza.

dist = vector<int>(n + 1, -1);
q = queue<int>();
for (i = 1; i <= n; i++)

  if (used[i] == 0)
  {
    q.push(i);
    dist[i] = 0;
  }

C++

Avviamo la ricerca in ampiezza multi-sorgente. Estraiamo dalla coda il vertice $v$ . Ogni suo vicino non visitato $t o (d i s t [t o] = -1)$ to~(dist[to] = –1) riceve la distanza $d i s t [v] + 1$ dist[v] + 1 e viene inserito nella coda. I vertici del ciclo sono contrassegnati con distanza $0$ fin dall'inizio, pertanto l'attraversamento non ritorna sull'anello e si propaga solo in profondità negli alberi pendenti. Poiché i vertici vengono estratti dalla coda in ordine non decrescente di distanza, ogni valore $d i s t [t o]$ dist[to] è il più breve possibile.

while (!q.empty())
{
  int v = q.front(); q.pop();
  for (int to : g[v])
    if (dist[to] == -1)
    {
      q.push(to);
      dist[to] = dist[v] + 1;
    }
  }

C++

Stampiamo le distanze dalle stazioni fino alla linea circolare in ordine dei loro numeri.

for (i = 1; i <= n; i++)
   printf("%d ", dist[i]);
printf("\n");