Точки зчленування (Розбір)

Точки зчленування шукаються за допомогою пошуку в глибину. Для кожної вершини $v$ обчислюються дві мітки:

$d [v]$ — час входу у вершину $v$ при обході в глибину;
$u p [v]$ — мінімальний час входу серед вершин, до яких можна потрапити з піддерева з коренем у $v$ , пройшовши по одному зворотному ребру.

Вершина $v$ , яка не є коренем дерева обходу, є точкою зчленування, якщо у неї є син $t o$ у дереві обходу в глибину, для якого виконується нерівність $u p [t o] \geq d [v]$ up[to] \ge d[v]. Ця нерівність означає, що з піддерева з коренем у $t o$ по зворотних ребрах не можна піднятися вище вершини $v$ . Тому при видаленні $v$ це піддерево виявиться відрізаним від решти графа.

Корінь дерева обходу є точкою зчленування тоді і тільки тоді, коли у нього в дереві обходу не менше двох синів.

Приклад

Граф з прикладу має такий вигляд:

Жирними лініями виділені ребра дерева обходу в глибину. Поряд з кожною вершиною $v$ вказані мітки $d [v] / u p [v]$ d[v] / up[v]. Точки зчленування виділені кольором.

Вершина 1 — корінь дерева обходу. Вона є точкою зчленування, оскільки у неї в дереві обходу два сини: вершини $2$ і $4$ .
Вершина 2 — точка зчленування, оскільки для ребра дерева $(2, 6)$ виконується $u p [6] \geq d [2] (2 \geq 2)$ up[6] \ge d[2]~(2 \ge 2).
Вершина 3 — точка зчленування, оскільки для ребра дерева $(3, 8)$ виконується $u p [8] \geq d [3] (3 \geq 3)$ up[8] \ge d[3]~(3 \ge 3).

Реалізація алгоритму

Граф зберігається у вигляді списку суміжності $g$ . Масив $u se d$ позначає відвідані вершини, у масивах $d$ і $u p$ зберігаються однойменні мітки. Змінна $t im er$ містить поточний час обходу в глибину. Знайдені точки зчленування збираються у множині $A r tP$ : вона виключає повтори і зберігає вершини у порядку зростання.

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

Функція dfs виконує пошук в глибину з вершини $v$ і попутно знаходить точки зчленування. Параметр $p$ — батько вершини $v$ у дереві обходу. Для кореня дерева $p = - 1$ p = -1, це значення за замовчуванням.

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

При вході у вершину $v$ позначаємо її як відвідану. Мітки $d [v]$ і $u p [v]$ отримують поточне значення таймера, після чого таймер збільшується.

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

Змінна $c hi l d r e n$ children рахує синів вершини $v$ у дереві обходу; це число знадобиться, якщо $v$ виявиться коренем.

  int children = 0;

Перебираємо вершини $t o$ , суміжні з $v$ . Ребро $(v, t o)$ (v, to) може бути одного з трьох видів:

ребро дерева, що переглядається у зворотному напрямку, до батька ( $t o = p$ to = p). Таке ребро пропускаємо;
зворотне ребро (вершина $t o$ вже відвідана і $t o \neq = p$ to \ne p);
ребро дерева, що веде у ще не відвідану вершину $t o$ .

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

Якщо вершина $t o$ вже відвідана, то $(v, t o)$ (v, to) — зворотне ребро. Перераховуємо значення $u p [v]$ .

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

Інакше $(v, t o)$ (v, to) — ребро дерева. Запускаємо пошук в глибину з вершини $t o$ , її батьком стає $v$ . Після повернення з рекурсії перераховуємо значення $u p [v]$ .

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

Якщо $u p [t o] \geq d [v]$ up[to] \ge d[v] і вершина $v$ не є коренем ( $p \neq = - 1$ p \ne -1), то $v$ — точка зчленування: з піддерева з коренем у $t o$ не можна піднятися вище $v$ , тому видалення $v$ відріже це піддерево від решти графа.

      if (up[to] >= d[v] && p != -1) // некоренева вершина
        ArtP.insert(v);

Вершина $t o$ — черговий син $v$ у дереві обходу, збільшуємо лічильник $c hi l d r e n$ children.

      children++;
    }
  }

Корінь дерева обходу ( $p = - 1$ p = -1) є точкою зчленування тоді і тільки тоді, коли у нього більше одного сина.

  if (p == -1 && children > 1)       // корінь DFS-дерева
    ArtP.insert(v);
}

Основна частина програми. Читаємо вхідні дані.

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

Граф неорієнтований, тому кожне ребро $(a, b)$ додаємо до списків суміжності обох його кінців.

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

Виділяємо пам'ять під масиви $d$ , $u p$ і $u se d$ .

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

Ініціалізуємо таймер і запускаємо пошук в глибину з кожної ще не відвіданої вершини: граф може бути незв'язним.

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

Виводимо кількість точок зчленування, а потім самі вершини. Множина $A r tP$ впорядкована, тому вершини виводяться у порядку зростання.

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

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

Python реалізація

Збільшимо максимальну глибину рекурсії.

import sys
sys.setrecursionlimit(10**6)

Граф зберігається у вигляді списку суміжності $g$ . Список $u se d$ позначає відвідані вершини, у списках $d$ і $u p$ зберігаються однойменні мітки. Знайдені точки зчленування збираються у множині $A r tP o in t s$ ArtPoints.

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

Функція dfs виконує пошук в глибину з вершини $v$ і попутно знаходить точки зчленування. Параметр $p$ — батько вершини $v$ у дереві обходу; для кореня $p = - 1$ p = -1. Змінна $c hi l d r e n$ children рахує синів вершини $v$ у дереві обходу.

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

При вході у вершину $v$ позначаємо її як відвідану. Мітки $d [v]$ і $u p [v]$ отримують поточне значення $t$ , після чого $t$ збільшується.

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

Перебираємо вершини $t o$ , суміжні з $v$ . Ребро $(v, t o)$ (v, to) може бути одного з трьох видів:

ребро дерева, що переглядається у зворотному напрямку, до батька ( $t o = p$ to = p). Таке ребро пропускаємо;
зворотне ребро (вершина $t o$ вже відвідана і $t o \neq = p$ to \ne p);
3. ребро дерева, що веде у ще не відвідану вершину $t o$ .

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

Якщо вершина $t o$ вже відвідана, то $(v, t o)$ (v, to) — зворотне ребро. Перераховуємо значення $u p [v]$ .

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

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

Якщо $u p [t o] \geq d [v]$ up[to] \ge d[v] і вершина $v$ не є коренем $(p \neq = - 1)$ (p ≠ -1), то $v$ — точка зчленування.

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

Вершина $t o$ — черговий син $v$ у дереві обходу, збільшуємо лічильник $c hi l d r e n$ children.

      children += 1

Корінь дерева обходу $(p = - 1)$ (p = -1) є точкою зчленування тоді і тільки тоді, коли у нього більше одного сина.

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

Основна частина програми. Створюємо списки і читаємо вхідні дані.

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

Читаємо ребра неорієнтованого графа і заповнюємо списки суміжності.

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

Запускаємо пошук в глибину з кожної ще не відвіданої вершини: граф може бути незв'язним.

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

Виводимо кількість точок зчленування, а потім самі вершини у порядку зростання.

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