Puntos de articulación (Editorial)

Los puntos de articulación se buscan mediante búsqueda en profundidad. Para cada vértice $v$ se calculan dos marcas:

$d [v]$ — el tiempo de entrada al vértice $v$ durante el recorrido en profundidad;
$u p [v]$ — el mínimo tiempo de entrada entre los vértices a los que se puede llegar desde el subárbol con raíz en $v$ , pasando por una sola arista de retroceso.

Un vértice $v$ , que no es la raíz del árbol de recorrido, es un punto de articulación si tiene un hijo $t o$ en el árbol de recorrido en profundidad, para el cual se cumple la desigualdad $u p [t o] \geq d [v]$ up[to] \ge d[v]. Esta desigualdad significa que desde el subárbol con raíz en $t o$ , siguiendo aristas de retroceso, no se puede subir más arriba que el vértice $v$ . Por lo tanto, al eliminar $v$ , este subárbol quedará desconectado del resto del grafo.

La raíz del árbol de recorrido es un punto de articulación si y solo si tiene al menos dos hijos en el árbol de recorrido.

Ejemplo

El grafo del ejemplo tiene la siguiente forma:

Las líneas en negrita indican las aristas del árbol de recorrido en profundidad. Junto a cada vértice $v$ se indican las marcas $d [v] / u p [v]$ d[v] / up[v]. Los puntos de articulación están resaltados en color.

Vértice 1 — es la raíz del árbol de recorrido. Es un punto de articulación, ya que tiene dos hijos en el árbol de recorrido: los vértices $2$ y $4$ .
Vértice 2 — es un punto de articulación, ya que para la arista del árbol $(2, 6)$ se cumple $u p [6] \geq d [2] (2 \geq 2)$ up[6] \ge d[2]~(2 \ge 2).
Vértice 3 — es un punto de articulación, ya que para la arista del árbol $(3, 8)$ se cumple $u p [8] \geq d [3] (3 \geq 3)$ up[8] \ge d[3]~(3 \ge 3).

Implementación del algoritmo

El grafo se almacena como una lista de adyacencia $g$ . El arreglo $u se d$ marca los vértices visitados, y los arreglos $d$ y $u p$ almacenan las marcas del mismo nombre. La variable $t im er$ contiene el tiempo actual del recorrido en profundidad. Los puntos de articulación encontrados se recolectan en el conjunto $A r tP$ : este excluye repeticiones y almacena los vértices en orden ascendente.

vector<vector<int>> g;
vector<int> d, up, used;
set<int> ArtP;

La función dfs realiza la búsqueda en profundidad desde el vértice $v$ y, de paso, encuentra los puntos de articulación. El parámetro $p$ — es el padre del vértice $v$ en el árbol de recorrido. Para la raíz del árbol, $p = - 1$ p = -1, este es el valor por defecto.

void dfs(int v, int p = -1)
{

Al entrar en el vértice $v$ , lo marcamos como visitado. Las marcas $d [v]$ y $u p [v]$ reciben el valor actual del temporizador, después de lo cual el temporizador se incrementa.

  used[v] = true;
  d[v] = up[v] = timer++;

La variable $c hi l d r e n$ children cuenta los hijos del vértice $v$ en el árbol de recorrido; este número será necesario si $v$ resulta ser la raíz.

  int children = 0;

Recorremos los vértices $t o$ adyacentes a $v$ . La arista $(v, t o)$ (v, to) puede ser de uno de tres tipos:

una arista del árbol, examinada en dirección inversa, hacia el padre ( $t o = p$ to = p). Esta arista se omite;
una arista de retroceso (el vértice $t o$ ya está visitado y $t o \neq = p$ to \ne p);
una arista del árbol, que lleva a un vértice $t o$ aún no visitado.

  for (int to : g[v])
  {
    if (to == p) continue;

Si el vértice $t o$ ya está visitado, entonces $(v, t o)$ (v, to) — es una arista de retroceso. Recalculamos el valor de $u p [v]$ .

    if (used[to])
      up[v] = min(up[v], d[to]);   // back edge
    else
    {

De lo contrario, $(v, t o)$ (v, to) — es una arista del árbol. Iniciamos la búsqueda en profundidad desde el vértice $t o$ , cuyo padre pasa a ser $v$ . Después de regresar de la recursión, recalculamos el valor de $u p [v]$ .

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

Si $u p [t o] \geq d [v]$ up[to] \ge d[v] y el vértice $v$ no es la raíz ( $p \neq = - 1$ p \ne -1), entonces $v$ — es un punto de articulación: desde el subárbol con raíz en $t o$ no se puede subir más arriba que $v$ , por lo que eliminar $v$ cortará este subárbol del resto del grafo.

      if (up[to] >= d[v] && p != -1) // vértice no raíz
        ArtP.insert(v);

El vértice $t o$ — es otro hijo de $v$ en el árbol de recorrido, incrementamos el contador $c hi l d r e n$ children.

      children++;
    }
  }

La raíz del árbol de recorrido ( $p = - 1$ p = -1) es un punto de articulación si y solo si tiene más de un hijo.

  if (p == -1 && children > 1)       // raíz del árbol DFS
    ArtP.insert(v);
}

Parte principal del programa. Leemos los datos de entrada.

scanf("%d %d", &n, &m);
g.resize(n + 1);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);

El grafo es no dirigido, por lo que cada arista $(a, b)$ se añade a las listas de adyacencia de ambos extremos.

  g[a].push_back(b);
  g[b].push_back(a);
}

Reservamos memoria para los arreglos $d$ , $u p$ y $u se d$ .

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

Inicializamos el temporizador e iniciamos la búsqueda en profundidad desde cada vértice aún no visitado: el grafo puede ser no conexo.

timer = 1;
for (int i = 1; i <= n; i++)
  if (!used[i]) dfs(i);

Mostramos la cantidad de puntos de articulación, y luego los propios vértices. El conjunto $A r tP$ está ordenado, por lo que los vértices se muestran en orden ascendente.

printf("%d\n", ArtP.size());
for (int v : ArtP)
  printf("%d\n", v);

Implementación en Java

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;
  static int used[], d[], up[];
  static int time;
  static TreeSet<Integer> ArtPoints = new TreeSet<Integer>();
  
  static void dfs (int v, int p)
  {
    int i, to, children;
    used[v] = 1;
    d[v] = up[v] = time++;
    children = 0;
    for (i = 0; i < g[v].size(); i++) 
    {
      to = g[v].get(i);
      if (to == p)  continue;
      if (used[to] == 1)
        up[v] = Math.min(up[v], d[to]);
      else 
      {
        dfs (to, v);
        up[v] = Math.min(up[v], up[to]);
        if ((up[to] >= d[v]) && (p != -1)) ArtPoints.add(v);
        children++;
      }
    }
    if ((p == -1) && (children > 1)) ArtPoints.add(v);
  }

  @SuppressWarnings("unchecked") 
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    g = new ArrayList[n+1]; // unchecked
    used = new int[n+1];
    d = new int[n+1];
    up = new int[n+1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();
   
    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g[a].add(b);
      g[b].add(a);
    }
    
    time = 1;
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i,-1);
    
    System.out.println(ArtPoints.size());
    for(int i : ArtPoints)
      System.out.println(i);
    con.close();
  }
}

Java

Implementación en Python

Aumentemos la profundidad máxima de recursión.

import sys
sys.setrecursionlimit(10**6)

El grafo se almacena como una lista de adyacencia $g$ . La lista $u se d$ marca los vértices visitados, y en las listas $d$ y $u p$ se almacenan las marcas del mismo nombre. Los puntos de articulación encontrados se recolectan en el conjunto $A r tP o in t s$ ArtPoints.

g = []
used = []
d = []
up = []
ArtPoints = set()

La función dfs realiza la búsqueda en profundidad desde el vértice $v$ y, de paso, encuentra los puntos de articulación. El parámetro $p$ — es el padre del vértice $v$ en el árbol de recorrido; para la raíz, $p = - 1$ p = -1. La variable $c hi l d r e n$ children cuenta los hijos del vértice $v$ en el árbol de recorrido.

def dfs(v, p = -1):
  global t
  children = 0

Al entrar en el vértice $v$ , lo marcamos como visitado. Las marcas $d [v]$ y $u p [v]$ reciben el valor actual de $t$ , después de lo cual $t$ se incrementa.

  used[v] = 1
  d[v] = up[v] = t
  t += 1

Recorremos los vértices $t o$ adyacentes a $v$ . La arista $(v, t o)$ (v, to) puede ser de uno de tres tipos:

una arista del árbol, examinada en dirección inversa, hacia el padre ( $t o = p$ to = p). Esta arista se omite;
una arista de retroceso (el vértice $t o$ ya está visitado y $t o \neq = p$ to \ne p);
3. una arista del árbol, que lleva a un vértice $t o$ aún no visitado.

  for to in g[v]:
    if to == p: continue

Si el vértice $t o$ ya está visitado, entonces $(v, t o)$ (v, to) — es una arista de retroceso. Recalculamos el valor de $u p [v]$ .

    if used[to]:
      up[v] = min(up[v], d[to])
    else:

      dfs(to, v)
      up[v] = min(up[v], up[to])

Si $u p [t o] \geq d [v]$ up[to] \ge d[v] y el vértice $v$ no es la raíz $(p \neq = - 1)$ (p ≠ -1), entonces $v$ — es un punto de articulación.

      if up[to] >= d[v] and p != -1:
        ArtPoints.add(v)

El vértice $t o$ — es otro hijo de $v$ en el árbol de recorrido, incrementamos el contador $c hi l d r e n$ children.

      children += 1

La raíz del árbol de recorrido $(p = - 1)$ (p = -1) es un punto de articulación si y solo si tiene más de un hijo.

    if p == -1 and children > 1:
      ArtPoints.add(v)

Parte principal del programa. Creamos las listas y leemos los datos de entrada.

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)
d = [0] * (n + 1)
up = [0] * (n + 1)

Leemos las aristas del grafo no dirigido y llenamos las listas de adyacencia.

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Iniciamos la búsqueda en profundidad desde cada vértice aún no visitado: el grafo puede ser no conexo.

t = 1
for i in range(1, n + 1):
  if not used[i]: dfs(i)

Mostramos la cantidad de puntos de articulación, y luego los propios vértices en orden ascendente.

print(len(ArtPoints))
for x in sorted(ArtPoints):
  print(x)