Мости#1943

Мости (Розбір)

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

Запустимо пошук у глибину. Кожне ребро графа виявиться або ребром дерева пошуку, або зворотним ребром. Зворотне ребро разом зі шляхом по дереву між його кінцями утворює цикл, тому мостом воно бути не може. Отже, мостами можуть бути лише ребра дерева пошуку.

Під час пошуку для кожної вершини $v$ обчислимо дві мітки:

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

Розглянемо ребро дерева $(v, t o)$ (v, to), де $t o$ — син вершини $v$ . Можливі три випадки:

$u p [t o] < d [v]$ up[to] < d[v]. З деякої вершини піддерева $t o$ веде зворотне ребро до власного предка вершини $v$ . Іншими словами, з вершини $v$ або її нащадка існує зворотне ребро до предка $v$ тоді і тільки тоді, коли у $v$ знайдеться такий син $t o$ , що $u p [t o] < d [v]$ up[to] < d[v].
$u p [t o] = d [v]$ up[to] = d[v]. Піддерево $t o$ містить зворотне ребро, яке веде рівно у вершину $v$ .
$u p [t o] > d [v]$ up[to] > d[v]. Жодна вершина піддерева $t o$ не може досягти вершини $v$ або її предків, не проходячи по ребру $(v, t o)$ (v, to). Отже, ребро $(v, t o)$ (v, to) є мостом.

У перших двох випадках ребро $(v, t o)$ (v, to) лежить на циклі і мостом не є. Таким чином, отримуємо критерій:

Теорема. Ребро дерева пошуку $(v, t o)$ (v, to), де $t o$ — син вершини $v$ , є мостом тоді і тільки тоді, коли $u p [t o] > d [v]$ up[to] > d[v].

Пошук у глибину виконується за $O (n + m)$ O(n + m). Номери знайдених мостів сортуються перед виведенням.

Приклад

Граф, наведений у прикладі, має такий вигляд. Поряд з кожним ребром вказано його номер у вхідних даних:

Запустимо пошук у глибину з вершини $1$ . Сусідів кожної вершини будемо переглядати у порядку появи ребер у вхідних даних. Обхід відвідує вершини у порядку $1, 2, 3, 4, 5, 6$ 1, 2, 3, 4, 5, 6. Ребрами дерева пошуку стають ребра $1, 2, 3, 5$ 1, 2, 3, 5 і $7$ , а ребра $4 = (3, 1)$ 4 = (3, 1) і $6 = (6, 4)$ 6 = (6, 4) виявляються зворотними.

Перевіримо умову $u p [t o] > d [v]$ up[to] > d[v] для всіх ребер дерева:

Ребро $(v, t o)$ (v, to)	Номер	$u p [t o]$	$d [v]$	Висновок
$(1, 2)$	1	1	1	$u p [2] = d [1]$ up[2] = d[1], не міст
$(2, 3)$	2	1	2	$u p [3] < d [2]$ up[3] < d[2], не міст
$(3, 4)$	3	4	3	$u p [4] > d [3]$ up[4] > d[3], міст
$(4, 5)$	5	4	4	$u p [5] = d [4]$ up[5] = d[4], не міст
$(5, 6)$	7	4	5	$u p [6] < d [5]$ up[6] < d[5], не міст

Таким чином, у графі рівно один міст — ребро номер $3$ , що з'єднує вершини $3$ і $4$ .

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

Граф зберігаємо у вигляді списку суміжності $g$ . Для кожної вершини $v$ у $g [v]$ записані пари $(t o, i d)$ (to, id), де $t o$ — сусідня вершина, а $i d$ — номер ребра $(v, t o)$ (v, to) у вхідних даних. Номер ребра потрібен з двох причин: щоб під час обходу не повертатися по тому самому ребру, по якому прийшли, і щоб виводити мости не як пари вершин, а як номери вхідних ребер.

Масиви $d$ і $u p$ містять мітки $d [v]$ і $u p [v]$ . Нульове значення $d [v]$ означає, що вершина $v$ ще не відвідана. У масиві $b r i d g es$ bridges збираємо номери ребер, які є мостами.

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

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

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

Перебираємо всі ребра $(v, t o)$ (v, to), що виходять з вершини $v$ . Ребро з номером $p$ пропускаємо: по ньому ми прийшли у $v$ , і воно веде до батька.

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

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

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

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

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

Якщо $u p [t o] > d [v]$ up[to] > d[v], то з піддерева $t o$ не можна потрапити у $v$ або її предків, минаючи ребро $(v, t o)$ (v, to), тому ребро з номером $i d$ є мостом.

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

Основна частина програми. Читаємо вхідний граф. Кожне ребро $(a, b)$ додаємо у списки суміжності обох вершин разом з його номером $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++

Ініціалізуємо масиви міток.

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

Змінна $t im er$ зберігає поточний час пошуку.

timer = 1;

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

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

Сортуємо номери мостів за зростанням.

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

Виводимо кількість мостів, а в наступному рядку — їхні номери.

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