Сильна зв'язність (Розбір)

Задача вимагає знайти кількість компонент сильної зв'язності орієнтованого графа. Для цього використовуємо алгоритм Косарайю, який виконує два обходи в глибину:

виконати обхід у глибину на вхідному графі та запам'ятати вершини в порядку завершення їх обробки (у момент виходу з вершини);
побудувати обернений граф, змінивши напрямок кожного ребра на протилежний;
перебрати вершини у зворотному порядку завершення їх обробки та запустити обхід у глибину на оберненому графі з кожної вершини, яка ще не була відвідана. Кожен такий запуск обходить рівно одну компоненту сильної зв'язності.

Обернений граф має ті самі компоненти сильної зв'язності, що й початковий: якщо існують шляхи з $u$ в $v$ і з $v$ в $u$ , то після зміни напрямку ребер ці шляхи зберігаються, змінюється лише їх напрямок. Порядок обробки вершин у другому обході гарантує, що обхід у глибину не вийде за межі поточної компоненти: усі компоненти, до яких він міг би дістатися, на цей момент уже відвідані.

Відповіддю є кількість запусків обходу в глибину під час другого обходу.

Приклад

Графи, наведені в прикладах, зображено нижче. Компоненти сильної зв'язності виділено кольором.

Перший граф не містить циклів: повернутися до жодної вершини неможливо. Тому кожна вершина утворює окрему компоненту сильної зв'язності: ${1}$ , ${2}$ , ${3}$ .

У другому графі вершини $1$ , $2$ і $3$ лежать на циклі $1 \to 2 \to 3 \to 1$ 1 \to 2 \to 3 \to 1 та утворюють одну компоненту ${1, 2, 3}$ \{1, 2, 3\}. Вершина $4$ недосяжна з вершини $5$ , тому вершини $4$ і $5$ утворюють окремі компоненти ${4}$ та ${5}$ . Отже, кожен із графів містить $3$ компоненти сильної зв'язності.

Просимулюємо роботу алгоритму на другому графі. Перший обхід у глибину з вершини $1$ проходить шлях $1 \to 2 \to 3$ 1 \to 2 \to 3, а потім з вершини $4$ — шлях $4 \to 5$ 4 \to 5. Порядок завершення обробки вершин: $t o p = (3, 2, 1, 5, 4)$ top = (3, 2, 1, 5, 4). Після інвертування отримуємо $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3).

Обернений граф містить ребра $2 \to 1$ 2 \to 1, $3 \to 2$ 3 \to 2, $1 \to 3$ 1 \to 3 та $5 \to 4$ 5 \to 4. Виконаємо другий обхід у порядку $(4, 5, 1, 2, 3)$ (4, 5, 1, 2, 3):

$df s 2 (4)$ : вершина $4$ не має вихідних ребер в оберненому графі, компонента ${4}$ ;
$df s 2 (5)$ : ребро $5 \to 4$ 5 \to 4 веде до вже відвіданої вершини, компонента ${5}$ ;
$df s 2 (1)$ : обхід шляху $1 \to 3 \to 2$ 1 \to 3 \to 2, компонента ${1, 3, 2}$ \{1, 3, 2\}.

Вершини $2$ і $3$ вже відвідано, тому нових запусків немає. Отримуємо $c = 3$ c = 3 компоненти.

Зауважимо, що в оберненому графі вершина $4$ , яка належить іншій компоненті, досяжна з вершини $5$ . Проте вершина $4$ обробляється раніше вершини $5$ , тому на момент виклику $df s 2 (5)$ вона вже відвідана і не потрапляє до компоненти вершини $5$ .

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

Зберігатимемо вхідний граф у вигляді списку суміжності $g$ , а обернений граф — у вигляді списку суміжності $g r$ . Масив $u se d$ позначає відвідані вершини. Масив $t o p$ зберігає вершини в порядку завершення їх обробки під час першого обходу в глибину.

vector\u003cvector\u003cint\u003e \u003e g, gr;
vector\u003cint\u003e used, top;

Функція dfs1 виконує обхід у глибину на вхідному графі. Вершина $v$ додається в кінець масиву $t o p$ після того, як оброблено всі вершини, досяжні з неї, тобто в момент виходу з неї.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

C++

Функція dfs2 виконує обхід у глибину на оберненому графі. Усі вершини, відвідані за один виклик $df s 2$ з основної програми, утворюють одну компоненту сильної зв'язності.

void dfs2(int v)
{
  used[v] = 1;
  for (int to : gr[v])
    if (!used[to]) dfs2(to);
}

Основна частина програми. Зчитуємо вхідний граф. Кожне ребро $a \to b$ a \to b додаємо до графа $g$ , а протилежне ребро $b \to a$ b \to a — до оберненого графа $g r$ .

scanf("%d %d", \u0026n, \u0026m);
g.resize(n + 1);
gr.resize(n + 1);
for(i = 1; i \u003c= m; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);
  gr[b].push_back(a);
}

C++

Запускаємо обхід у глибину на вхідному графі з кожної вершини, яка ще не була відвідана. Після цього масив $t o p$ містить усі вершини графа в порядку завершення їх обробки.

used.resize(n+1);
for(i = 1; i \u003c= n; i++)
  if (!used[i]) dfs1(i);

Перед другим обходом обнулимо масив $u se d$ . Вершини оберненого графа потрібно розглядати у зворотному порядку завершення їх обробки, тобто масив $t o p$ потрібно переглянути від кінця до початку. Для зручності обернемо масив $t o p$ .

used.assign(n + 1, 0);
reverse(top.begin(), top.end());

Змінна $c$ підраховує кількість компонент сильної зв'язності.

c = 0;

Пройдемо масивом $t o p$ зліва направо. З кожної ще не відвіданої вершини $v$ запускаємо обхід у глибину dfs2 на оберненому графі. Він обходить рівно одну нову компоненту сильної зв'язності, тому збільшуємо $c$ на $1$ .

for (int v : top)
  if (!used[v])
  {
    dfs2(v);
    c++;
  }

Виводимо кількість компонент сильної зв'язності графа.

printf("%d\n",c);

Реалізація мовою Java

import java.util.*;

public class Main
{
  static ArrayList\u003cInteger\u003e[] g, gr;
  static boolean used[];
  static Vector\u003cInteger\u003e top = new Vector\u003cInteger\u003e();

  static void dfs1(int v)
  {
    used[v] = true;
    for(int i = 0; i \u003c g[v].size(); i++)
    {
      int to = g[v].get(i);
      if (!used[to]) dfs1(to);
    }
    top.add(v);
  }

  static void dfs2(int v)
  {
    used[v] = true;
    for(int i = 0; i \u003c gr[v].size(); i++)
    {
      int to = gr[v].get(i);
      if (!used[to]) dfs2(to);
    }
  }

  @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];
    for(int i = 0; i \u003c= n; i++)
      g[i] = new ArrayList\u003cInteger\u003e();
    gr = new ArrayList[n+1];
    for(int i = 0; i \u003c= n; i++)
      gr[i] = new ArrayList\u003cInteger\u003e();

    for (int i = 0; i \u003c m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a].add(b);
      gr[b].add(a);
    }
    used = new boolean[n+1];
    for(int i = 1; i \u003c= n; i++)
      if (!used[i]) dfs1(i);

    used = new boolean[n+1];
    int c = 0;
    for(int i = 1; i \u003c= n; i++)
    {
      int v = top.get(n-i);
      if (!used[v])
      {
        dfs2(v);
        c++;
      }
    }

    System.out.println(c);
    con.close();
  }
}

Java

Реалізація мовою Python

Функція dfs1 виконує обхід у глибину на вхідному графі. Вершина $v$ додається в кінець списку $t o p$ після того, як оброблено всі вершини, досяжні з неї, тобто в момент виходу з неї.

def dfs1(v):
  global g, used, top
  used[v] = True
  for to in g[v]:
    if not used[to]: dfs1(to)
  top.append(v)

def dfs2(v):
  global gr, used
  used[v] = True
  for to in gr[v]:
    if not used[to]: dfs2(to)

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

Python

Запускаємо обхід у глибину на вхідному графі з кожної вершини, яка ще не була відвідана. Після цього список $t o p$ містить усі вершини графа в порядку завершення їх обробки.

used = [False] * (n + 1)
top = []
for i in range(1, n + 1):
  if not used[i]: dfs1(i)

Перед другим обходом обнулимо список $u se d$ . Вершини оберненого графа потрібно розглядати у зворотному порядку завершення їх обробки, тому обернемо список $t o p$ .

used = [False] * (n + 1)
top.reverse()

Змінна $c$ підраховує кількість компонент сильної зв'язності.

c = 0

Пройдемо списком $t o p$ зліва направо. З кожної ще не відвіданої вершини $v$ запускаємо обхід у глибину dfs2 на оберненому графі. Він обходить рівно одну нову компоненту сильної зв'язності, тому збільшуємо $c$ на $1$ .

for v in top:
  if not used[v]:
    dfs2(v)
    c += 1

Виводимо кількість компонент сильної зв'язності графа.

print(c)