Мосты#1943

Мосты (Editorial)

Un puente es una arista cuya eliminación aumenta el número de componentes conexas del grafo. Una arista es un puente si y solo si no se encuentra en ningún ciclo simple: si una arista pertenece a un ciclo, entonces, tras su eliminación, los extremos de la arista permanecen conectados por el resto del ciclo.

Ejecutemos una búsqueda en profundidad. Cada arista del grafo resultará ser una arista del árbol de búsqueda o una arista de retroceso. Una arista de retroceso, junto con el camino por el árbol entre sus extremos, forma un ciclo, por lo que no puede ser un puente. Por lo tanto, solo las aristas del árbol de búsqueda pueden ser puentes.

Durante la búsqueda, para cada vértice $v$ calcularemos dos etiquetas:

$d [v]$ — el tiempo de entrada al vértice $v$ , es decir, el número de orden con el que el vértice $v$ fue visitado por primera vez;
$u p [v]$ — el menor tiempo de entrada que se puede alcanzar desde el vértice $v$ , descendiendo por las aristas del árbol hacia sus descendientes y luego pasando por, como máximo, una arista de retroceso.

Consideremos una arista del árbol $(v, t o)$ (v, to), donde $t o$ es hijo del vértice $v$ . Son posibles tres casos:

$u p [t o] < d [v]$ up[to] < d[v]. Desde algún vértice del subárbol $t o$ parte una arista de retroceso hacia un ancestro propio del vértice $v$ . Dicho de otro modo, desde el vértice $v$ o alguno de sus descendientes existe una arista de retroceso hacia un ancestro de $v$ si y solo si $v$ tiene un hijo $t o$ tal que $u p [t o] < d [v]$ up[to] < d[v].
$u p [t o] = d [v]$ up[to] = d[v]. El subárbol $t o$ contiene una arista de retroceso que lleva exactamente al vértice $v$ .
$u p [t o] > d [v]$ up[to] > d[v]. Ningún vértice del subárbol $t o$ puede alcanzar al vértice $v$ ni a sus ancestros sin pasar por la arista $(v, t o)$ (v, to). Por lo tanto, la arista $(v, t o)$ (v, to) es un puente.

En los dos primeros casos, la arista $(v, t o)$ (v, to) se encuentra en un ciclo y no es un puente. De este modo, obtenemos el criterio:

Teorema. Una arista del árbol de búsqueda $(v, t o)$ (v, to), donde $t o$ es hijo del vértice $v$ , es un puente si y solo si $u p [t o] > d [v]$ up[to] > d[v].

La búsqueda en profundidad se ejecuta en $O (n + m)$ O(n + m). Los números de los puentes encontrados se ordenan antes de mostrarlos.

Ejemplo

El grafo presentado en el ejemplo tiene el siguiente aspecto. Junto a cada arista se indica su número en los datos de entrada:

Ejecutemos la búsqueda en profundidad desde el vértice $1$ . Recorreremos los vecinos de cada vértice en el orden en que aparecen las aristas en los datos de entrada. El recorrido visita los vértices en el orden $1, 2, 3, 4, 5, 6$ 1, 2, 3, 4, 5, 6. Las aristas del árbol de búsqueda resultan ser las aristas $1, 2, 3, 5$ 1, 2, 3, 5 y $7$ , mientras que las aristas $4 = (3, 1)$ 4 = (3, 1) y $6 = (6, 4)$ 6 = (6, 4) resultan ser de retroceso.

Comprobemos la condición $u p [t o] > d [v]$ up[to] > d[v] para todas las aristas del árbol:

Arista $(v, t o)$ (v, to)	Número	$u p [t o]$	$d [v]$	Resultado
$(1, 2)$	1	1	1	$u p [2] = d [1]$ up[2] = d[1], no es puente
$(2, 3)$	2	1	2	$u p [3] < d [2]$ up[3] < d[2], no es puente
$(3, 4)$	3	4	3	$u p [4] > d [3]$ up[4] > d[3], puente
$(4, 5)$	5	4	4	$u p [5] = d [4]$ up[5] = d[4], no es puente
$(5, 6)$	7	4	5	$u p [6] < d [5]$ up[6] < d[5], no es puente

Por lo tanto, en el grafo hay exactamente un puente: la arista número $3$ , que une los vértices $3$ y $4$ .

Implementación del algoritmo

El grafo se almacena como una lista de adyacencia $g$ . Para cada vértice $v$ , en $g [v]$ se guardan pares $(t o, i d)$ (to, id), donde $t o$ es el vértice vecino e $i d$ es el número de la arista $(v, t o)$ (v, to) en los datos de entrada. El número de la arista es necesario por dos razones: para no retroceder durante el recorrido por la misma arista por la que se llegó, y para mostrar los puentes no como pares de vértices, sino como números de las aristas de entrada.

Los arreglos $d$ y $u p$ contienen las etiquetas $d [v]$ y $u p [v]$ . Un valor cero de $d [v]$ significa que el vértice $v$ aún no ha sido visitado. En el arreglo $b r i d g es$ bridges recopilamos los números de las aristas que son puentes.

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

La función dfs implementa la búsqueda en profundidad desde el vértice $v$ . El parámetro $p$ es el número de la arista por la cual llegamos al vértice $v$ . Para la raíz del árbol de búsqueda no existe tal arista, por lo que por defecto $p = - 1$ p = -1. Al entrar en un vértice, asignamos a $d [v]$ y $u p [v]$ el tiempo actual.

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

Recorremos todas las aristas $(v, t o)$ (v, to) que salen del vértice $v$ . La arista con número $p$ se omite: por ella llegamos a $v$ , y conduce al padre.

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

Si el vértice $t o$ ya ha sido visitado $(d [t o] \neq = 0)$ (d[to] \ne 0), entonces $(v, t o)$ (v, to) es una arista de retroceso. Recalculamos $u p [v]$ teniendo en cuenta el tiempo de entrada a $t o$ .

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

En caso contrario, $(v, t o)$ (v, to) es una arista del árbol. Lanzamos la búsqueda desde el vértice $t o$ , pasando el número de arista $i d$ . Tras el retorno, recalculamos $u p [v]$ a través de $u p [t o]$ .

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

Si $u p [t o] > d [v]$ up[to] > d[v], entonces desde el subárbol $t o$ no se puede llegar a $v$ ni a sus ancestros sin pasar por la arista $(v, t o)$ (v, to), por lo que la arista con número $i d$ es un puente.

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

Parte principal del programa. Leemos el grafo de entrada. Cada arista $(a, b)$ se añade a las listas de adyacencia de ambos vértices junto con su número $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++

Inicializamos los arreglos de etiquetas.

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

La variable $t im er$ almacena el tiempo actual de la búsqueda.

timer = 1;

El grafo puede ser no conexo, por lo que ejecutamos la búsqueda en profundidad desde cada vértice aún no visitado.

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

Ordenamos los números de los puentes en orden ascendente.

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

Mostramos la cantidad de puentes y, en la siguiente línea, sus números.

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