Punti di articolazione (Editoriale)

I punti di articolazione si cercano mediante la ricerca in profondità. Per ogni vertice $v$ vengono calcolate due etichette:

$d [v]$ — il tempo di ingresso nel vertice $v$ durante la visita in profondità;
$u p [v]$ — il tempo di ingresso minimo tra i vertici raggiungibili dal sottoalbero con radice in $v$ , percorrendo un solo arco all'indietro.

Un vertice $v$ , che non sia la radice dell'albero di visita, è un punto di articolazione se ha un figlio $t o$ nell'albero di visita in profondità, per il quale vale la disuguaglianza $u p [t o] \geq d [v]$ up[to] \ge d[v]. Questa disuguaglianza significa che dal sottoalbero con radice in $t o$ , tramite archi all'indietro, non è possibile risalire più in alto del vertice $v$ . Pertanto, rimuovendo $v$ , questo sottoalbero risulterà tagliato fuori dal resto del grafo.

La radice dell'albero di visita è un punto di articolazione se e solo se ha almeno due figli nell'albero di visita.

Esempio

Il grafo dell'esempio ha il seguente aspetto:

Con linee in grassetto sono evidenziati gli archi dell'albero di visita in profondità. Accanto a ogni vertice $v$ sono indicate le etichette $d [v] / u p [v]$ d[v] / up[v]. I punti di articolazione sono evidenziati con un colore.

Il vertice 1 — è la radice dell'albero di visita. È un punto di articolazione, poiché nell'albero di visita ha due figli: i vertici $2$ e $4$ .
Il vertice 2 — è un punto di articolazione, poiché per l'arco dell'albero $(2, 6)$ vale $u p [6] \geq d [2] (2 \geq 2)$ up[6] \ge d[2]~(2 \ge 2).
Il vertice 3 — è un punto di articolazione, poiché per l'arco dell'albero $(3, 8)$ vale $u p [8] \geq d [3] (3 \geq 3)$ up[8] \ge d[3]~(3 \ge 3).

Implementazione dell'algoritmo

Il grafo viene memorizzato come lista di adiacenza $g$ . L'array $u se d$ segna i vertici visitati, negli array $d$ e $u p$ sono memorizzate le omonime etichette. La variabile $t im er$ contiene il tempo corrente della visita in profondità. I punti di articolazione trovati vengono raccolti nell'insieme $A r tP$ : esso esclude i duplicati e mantiene i vertici in ordine crescente.

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

La funzione dfs esegue la ricerca in profondità a partire dal vertice $v$ e contestualmente trova i punti di articolazione. Il parametro $p$ — è il genitore del vertice $v$ nell'albero di visita. Per la radice dell'albero $p = - 1$ p = -1, questo è il valore predefinito.

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

All'ingresso nel vertice $v$ lo segniamo come visitato. Le etichette $d [v]$ e $u p [v]$ ricevono il valore corrente del timer, dopodiché il timer viene incrementato.

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

La variabile $c hi l d r e n$ children conta i figli del vertice $v$ nell'albero di visita; questo numero servirà se $v$ risulta essere la radice.

  int children = 0;

Scorriamo i vertici $t o$ adiacenti a $v$ . L'arco $(v, t o)$ (v, to) può essere di uno dei tre tipi:

un arco dell'albero, esaminato in direzione inversa, verso il genitore ( $t o = p$ to = p). Un tale arco viene saltato;
un arco all'indietro (il vertice $t o$ è già stato visitato e $t o \neq = p$ to \ne p);
un arco dell'albero che conduce a un vertice $t o$ non ancora visitato.

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

Se il vertice $t o$ è già stato visitato, allora $(v, t o)$ (v, to) — è un arco all'indietro. Ricalcoliamo il valore di $u p [v]$ .

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

Altrimenti $(v, t o)$ (v, to) — è un arco dell'albero. Avviamo la ricerca in profondità dal vertice $t o$ , il cui genitore diventa $v$ . Dopo il ritorno dalla ricorsione ricalcoliamo il valore di $u p [v]$ .

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

Se $u p [t o] \geq d [v]$ up[to] \ge d[v] e il vertice $v$ non è la radice ( $p \neq = - 1$ p \ne -1), allora $v$ — è un punto di articolazione: dal sottoalbero con radice in $t o$ non si può risalire più in alto di $v$ , quindi la rimozione di $v$ taglierà fuori questo sottoalbero dal resto del grafo.

      if (up[to] >= d[v] && p != -1) // vertice non radice
        ArtP.insert(v);

Il vertice $t o$ — è l'ennesimo figlio di $v$ nell'albero di visita, incrementiamo il contatore $c hi l d r e n$ children.

      children++;
    }
  }

La radice dell'albero di visita ( $p = - 1$ p = -1) è un punto di articolazione se e solo se ha più di un figlio.

  if (p == -1 && children > 1)       // radice dell'albero DFS
    ArtP.insert(v);
}

Parte principale del programma. Leggiamo i dati di input.

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

Il grafo è non orientato, quindi ogni arco $(a, b)$ viene aggiunto alle liste di adiacenza di entrambi i suoi estremi.

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

Allochiamo memoria per gli array $d$ , $u p$ e $u se d$ .

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

Inizializziamo il timer e avviamo la ricerca in profondità da ogni vertice non ancora visitato: il grafo potrebbe essere non connesso.

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

Stampiamo il numero di punti di articolazione, e poi i vertici stessi. L'insieme $A r tP$ è ordinato, quindi i vertici vengono stampati in ordine crescente.

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

Implementazione in 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

Implementazione in Python

Aumentiamo la profondità massima di ricorsione.

import sys
sys.setrecursionlimit(10**6)

Il grafo viene memorizzato come lista di adiacenza $g$ . La lista $u se d$ segna i vertici visitati, nelle liste $d$ e $u p$ sono memorizzate le omonime etichette. I punti di articolazione trovati vengono raccolti nell'insieme $A r tP o in t s$ ArtPoints.

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

La funzione dfs esegue la ricerca in profondità a partire dal vertice $v$ e contestualmente trova i punti di articolazione. Il parametro $p$ — è il genitore del vertice $v$ nell'albero di visita; per la radice $p = - 1$ p = -1. La variabile $c hi l d r e n$ children conta i figli del vertice $v$ nell'albero di visita.

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

All'ingresso nel vertice $v$ lo segniamo come visitato. Le etichette $d [v]$ e $u p [v]$ ricevono il valore corrente di $t$ , dopodiché $t$ viene incrementato.

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

Scorriamo i vertici $t o$ adiacenti a $v$ . L'arco $(v, t o)$ (v, to) può essere di uno dei tre tipi:

un arco dell'albero, esaminato in direzione inversa, verso il genitore ( $t o = p$ to = p). Un tale arco viene saltato;
un arco all'indietro (il vertice $t o$ è già stato visitato e $t o \neq = p$ to \ne p);
3. un arco dell'albero che conduce a un vertice $t o$ non ancora visitato.

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

Se il vertice $t o$ è già stato visitato, allora $(v, t o)$ (v, to) — è un arco all'indietro. Ricalcoliamo il valore di $u p [v]$ .

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

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

Se $u p [t o] \geq d [v]$ up[to] \ge d[v] e il vertice $v$ non è la radice $(p \neq = - 1)$ (p ≠ -1), allora $v$ — è un punto di articolazione.

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

Il vertice $t o$ — è l'ennesimo figlio di $v$ nell'albero di visita, incrementiamo il contatore $c hi l d r e n$ children.

      children += 1

La radice dell'albero di visita $(p = - 1)$ (p = -1) è un punto di articolazione se e solo se ha più di un figlio.

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

Parte principale del programma. Creiamo le liste e leggiamo i dati di input.

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

Leggiamo gli archi del grafo non orientato e riempiamo le liste di adiacenza.

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

Avviamo la ricerca in profondità da ogni vertice non ancora visitato: il grafo potrebbe essere non connesso.

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

Stampiamo il numero di punti di articolazione, e poi i vertici stessi in ordine crescente.

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