Ponti#1943

Ponti (Editoriale)

Si chiama ponte un arco la cui rimozione aumenta il numero di componenti connesse del grafo. Un arco è un ponte se e solo se non giace su alcun ciclo semplice: se un arco appartiene a un ciclo, dopo la sua rimozione gli estremi dell'arco restano collegati dal resto del ciclo.

Eseguiamo una visita in profondità (DFS). Ogni arco del grafo risulterà essere o un arco dell'albero di visita, oppure un arco all'indietro. Un arco all'indietro, insieme al percorso nell'albero tra i suoi estremi, forma un ciclo, quindi non può essere un ponte. Di conseguenza, solo gli archi dell'albero di visita possono essere ponti.

Durante la visita, per ogni vertice $v$ calcoliamo due etichette:

$d [v]$ — il tempo di ingresso nel vertice $v$ , ossia il numero progressivo con cui il vertice $v$ è stato visitato per la prima volta;
$u p [v]$ — il tempo di ingresso minimo raggiungibile dal vertice $v$ , scendendo lungo gli archi dell'albero verso i suoi discendenti e poi percorrendo al più un arco all'indietro.

Consideriamo un arco dell'albero $(v, t o)$ (v, to), dove $t o$ è figlio del vertice $v$ . Sono possibili tre casi:

$u p [t o] < d [v]$ up[to] < d[v]. Da un qualche vertice del sottoalbero di $t o$ parte un arco all'indietro verso un antenato proprio del vertice $v$ . In altre parole, dal vertice $v$ o da un suo discendente esiste un arco all'indietro verso un antenato di $v$ se e solo se $v$ possiede un figlio $t o$ tale che $u p [t o] < d [v]$ up[to] < d[v].
$u p [t o] = d [v]$ up[to] = d[v]. Il sottoalbero di $t o$ contiene un arco all'indietro che conduce esattamente al vertice $v$ .
$u p [t o] > d [v]$ up[to] > d[v]. Nessun vertice del sottoalbero di $t o$ può raggiungere il vertice $v$ o i suoi antenati senza passare per l'arco $(v, t o)$ (v, to). Di conseguenza, l'arco $(v, t o)$ (v, to) è un ponte.

Nei primi due casi l'arco $(v, t o)$ (v, to) giace su un ciclo e non è un ponte. Otteniamo così il seguente criterio:

Teorema. Un arco dell'albero di visita $(v, t o)$ (v, to), dove $t o$ è figlio del vertice $v$ , è un ponte se e solo se $u p [t o] > d [v]$ up[to] > d[v].

La visita in profondità viene eseguita in $O (n + m)$ O(n + m). I numeri dei ponti trovati vengono ordinati prima dell'output.

Esempio

Il grafo riportato nell'esempio ha il seguente aspetto. Accanto a ogni arco è indicato il suo numero nei dati di input:

Eseguiamo una visita in profondità a partire dal vertice $1$ . Esamineremo i vicini di ciascun vertice nell'ordine in cui gli archi compaiono nei dati di input. La visita raggiunge i vertici nell'ordine $1, 2, 3, 4, 5, 6$ 1, 2, 3, 4, 5, 6. Diventano archi dell'albero di visita gli archi $1, 2, 3, 5$ 1, 2, 3, 5 e $7$ , mentre gli archi $4 = (3, 1)$ 4 = (3, 1) e $6 = (6, 4)$ 6 = (6, 4) risultano essere archi all'indietro.

Verifichiamo la condizione $u p [t o] > d [v]$ up[to] > d[v] per tutti gli archi dell'albero:

Arco $(v, t o)$ (v, to)	Numero	$u p [t o]$	$d [v]$	Conclusione
$(1, 2)$	1	1	1	$u p [2] = d [1]$ up[2] = d[1], non è un ponte
$(2, 3)$	2	1	2	$u p [3] < d [2]$ up[3] < d[2], non è un ponte
$(3, 4)$	3	4	3	$u p [4] > d [3]$ up[4] > d[3], ponte
$(4, 5)$	5	4	4	$u p [5] = d [4]$ up[5] = d[4], non è un ponte
$(5, 6)$	7	4	5	$u p [6] < d [5]$ up[6] < d[5], non è un ponte

Quindi, nel grafo c'è esattamente un ponte — l'arco numero $3$ , che collega i vertici $3$ e $4$ .

Implementazione dell'algoritmo

Il grafo viene memorizzato come lista di adiacenza $g$ . Per ogni vertice $v$ , in $g [v]$ sono registrate coppie $(t o, i d)$ (to, id), dove $t o$ è il vertice adiacente e $i d$ è il numero dell'arco $(v, t o)$ (v, to) nei dati di input. Il numero dell'arco è necessario per due motivi: per non ripercorrere durante la visita lo stesso arco da cui siamo arrivati, e per restituire i ponti non come coppie di vertici, ma come numeri degli archi di input.

Gli array $d$ e $u p$ contengono le etichette $d [v]$ e $u p [v]$ . Il valore nullo di $d [v]$ significa che il vertice $v$ non è ancora stato visitato. Nell'array $b r i d g es$ bridges raccogliamo i numeri degli archi che sono ponti.

vector<vector<pair<int, int> > > g;
vector<int> d, up, bridges;

La funzione dfs implementa la visita in profondità a partire dal vertice $v$ . Il parametro $p$ è il numero dell'arco attraverso cui siamo arrivati al vertice $v$ . Per la radice dell'albero di visita tale arco non esiste, quindi per default $p = - 1$ p = -1. All'ingresso nel vertice assegniamo a $d [v]$ e $u p [v]$ il tempo corrente.

void dfs(int v, int p = -1)
{
  d[v] = up[v] = timer++;

Scorriamo tutti gli archi $(v, t o)$ (v, to) che escono dal vertice $v$ . Saltiamo l'arco con numero $p$ : è quello attraverso cui siamo arrivati a $v$ , e conduce al genitore.

  for (auto edge : g[v])
  {
    int to = edge.first;
    int id = edge.second;
    if (id == p) continue;

Se il vertice $t o$ è già stato visitato $(d [t o] \neq = 0)$ (d[to] \ne 0), allora $(v, t o)$ (v, to) è un arco all'indietro. Ricalcoliamo $u p [v]$ tenendo conto del tempo di ingresso in $t o$ .

    if (d[to] != 0)
      up[v] = min(up[v], d[to]);

Altrimenti, $(v, t o)$ (v, to) è un arco dell'albero. Avviamo la visita a partire dal vertice $t o$ , passando il numero dell'arco $i d$ . Dopo il ritorno, ricalcoliamo $u p [v]$ tramite $u p [t o]$ .

    else
    {
      dfs(to, id);
      up[v] = min(up[v], up[to]);

Se $u p [t o] > d [v]$ up[to] > d[v], allora dal sottoalbero di $t o$ non è possibile raggiungere $v$ o i suoi antenati senza passare per l'arco $(v, t o)$ (v, to), quindi l'arco con numero $i d$ è un ponte.

      if (up[to] > d[v]) bridges.push_back(id);
    }
  }
}

Parte principale del programma. Leggiamo il grafo in input. Ogni arco $(a, b)$ viene aggiunto alle liste di adiacenza di entrambi i vertici insieme al suo numero $i$ .

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

C++

Inizializziamo gli array delle etichette.

d.resize(n + 1);
up.resize(n + 1);

La variabile $t im er$ memorizza il tempo corrente della visita.

timer = 1;

Il grafo può essere non connesso, quindi avviamo la visita in profondità da ogni vertice non ancora visitato.

for (i = 1; i <= n; i++)
  if (d[i] == 0) dfs(i);

Ordiniamo i numeri dei ponti in ordine crescente.

sort(bridges.begin(), bridges.end());

Stampiamo il numero di ponti, e nella riga successiva i loro numeri.

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