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

Означення

Нехай $G=(V,E)$ — орієнтований граф з множиною вершин $V$ і множиною ребер $E \subseteq V \times V$. Позначимо через $n=|V|$ кількість вершин, а через $m=|E|$ — кількість ребер у $G$. Усі означення в цій статті легко узагальнити на мультиграфи, але ми на цьому не зосереджуватимемось.

Підмножину вершин $C \subseteq V$ називають компонентою сильної зв'язності, якщо виконуються такі умови:

• для всіх $u,v\in C$ при $u \neq v$ існує шлях з $u$ до $v$ і шлях з $v$ до $u$, і
• $C$ є максимальною в тому сенсі, що жодну вершину не можна додати, не порушивши наведену вище умову.

Позначимо через $\text{SCC}(G)$ множину компонент сильної зв'язності графа $G$. Ці компоненти сильної зв'язності не перетинаються між собою і покривають усі вершини графа. Отже, множина $\text{SCC}(G)$ є розбиттям множини $V$.

Розгляньмо граф $G_\text{example}$, у якому виділено компоненти сильної зв'язності:

Тут ми маємо $\text{SCC}(G_\text{example})=\{\{0,7\},\{1,2,3,5,6\},\{4,9\},\{8\}\}.$ Можемо переконатися, що в межах кожної компоненти сильної зв'язності всі вершини досяжні одна з одної.

Означимо граф конденсації $G^{\text{SCC}}=(V^{\text{SCC}}, E^{\text{SCC}})$ так:

• вершинами графа $G^{\text{SCC}}$ є компоненти сильної зв'язності графа $G$; тобто $V^{\text{SCC}} = \text{SCC}(G)$, і
• для всіх вершин $C_i,C_j$ графа конденсації існує ребро з $C_i$ до $C_j$ тоді й лише тоді, коли $C_i \neq C_j$ і існують такі $a\in C_i$ та $b\in C_j$, що в $G$ є ребро з $a$ до $b$.

Граф конденсації для $G_\text{example}$ виглядає так:

Найважливіша властивість графа конденсації полягає в тому, що він ациклічний. Справді, у графі конденсації за означенням немає «петель», а якби існував цикл, що проходить через дві або більше вершин (компонент сильної зв'язності) графа конденсації, то через досяжність об'єднання цих компонент сильної зв'язності саме мало б бути однією компонентою сильної зв'язності: суперечність.

Алгоритм, описаний у наступному розділі, знаходить усі компоненти сильної зв'язності в заданому графі. Після цього можна побудувати граф конденсації.

Коли підходить цей алгоритм?

• Граф орієнтований, і потрібно згрупувати вершини за взаємною досяжністю (з $u$ в $v$ і назад)? (якщо граф неорієнтований → пошук компонент зв'язності)
• Потрібно звести граф до ациклічного графа конденсації (наприклад, для ДП на DAG чи 2-SAT)?
• Достатньо двох проходів DFS за $O(n + m)$?

Алгоритм Косараджу

Опис алгоритму

Описаний алгоритм незалежно запропонували Косараджу та Sharir приблизно у 1980 році. Він ґрунтується на двох серіях пошуку в глибину і має час роботи $O(n + m)$.

На першому кроці алгоритму ми виконуємо послідовність пошуків у глибину (dfs), відвідуючи весь граф. Тобто доки ще є невідвідані вершини, ми беремо одну з них і запускаємо з неї пошук у глибину. Для кожної вершини ми відстежуємо час виходу $t_\text{out}[v]$. Це «мітка часу», у яку завершується виконання dfs для вершини $v$, тобто момент, коли всі досяжні з $v$ вершини вже відвідано і алгоритм повертається до $v$. Лічильник міток часу не слід скидати між послідовними викликами dfs. Часи виходу відіграють ключову роль в алгоритмі, що стане зрозумілим, коли ми розглянемо наступну теорему.

Спершу означимо час виходу $t_\text{out}[C]$ компоненти сильної зв'язності $C$ як максимум значень $t_\text{out}[v]$ по всіх $v \in C.$ Крім того, у доведенні теореми ми згадуватимемо час входу $t_{\text{in}}[v]$ для кожної вершини $v\in G$. Число $t_{\text{in}}[v]$ є «міткою часу», у яку на першому кроці алгоритму викликається рекурсивна функція dfs для вершини $v$. Для компоненти сильної зв'язності $C$ означимо $t_{\text{in}}[C]$ як мінімум значень $t_{\text{in}}[v]$ по всіх $v \in C$.

Теорема

Нехай $C$ і $C'$ — дві різні компоненти сильної зв'язності, і нехай у графі конденсації є ребро з $C$ до $C'$. Тоді $t_\text{out}[C] > t_\text{out}[C']$.

Доведення

Маємо два різні випадки залежно від того, якої компоненти першою досягне пошук у глибину:

• Випадок 1: компоненту $C$ було досягнуто першою (тобто $t_{\text{in}}[C] < t_{\text{in}}[C']$). У цьому випадку пошук у глибину відвідує деяку вершину $v \in C$ у момент, коли всі інші вершини компонент $C$ і $C'$ ще не відвідано. Оскільки в графі конденсації є ребро з $C$ до $C'$, то з $v$ у $G$ досяжні не лише всі інші вершини компоненти $C$, а й усі вершини компоненти $C'$. Це означає, що це виконання dfs, яке запущене з вершини $v$, у майбутньому також відвідає всі інші вершини компонент $C$ і $C'$, тож ці вершини будуть нащадками $v$ у дереві пошуку в глибину. Звідси випливає, що для кожної вершини $u \in (C \cup C')\setminus \{v\}$ маємо $t_\text{out}[v] > t_\text{out}[u]$. Отже, $t_\text{out}[C] > t_\text{out}[C']$, що завершує цей випадок доведення.

• Випадок 2: компоненту $C'$ було досягнуто першою (тобто $t_{\text{in}}[C] > t_{\text{in}}[C']$). У цьому випадку пошук у глибину відвідує деяку вершину $v \in C'$ у момент, коли всі інші вершини компонент $C$ і $C'$ ще не відвідано. Оскільки в графі конденсації є ребро з $C$ до $C'$, то через властивість ациклічності $C$ не досяжна з $C'$. Тому виконання dfs, запущене з вершини $v$, не досягне жодної вершини $C$, але відвідає всі вершини $C'$. Вершини $C$ буде відвідано пізнішим виконанням dfs на цьому ж кроці алгоритму, тож справді маємо $t_\text{out}[C] > t_\text{out}[C']$. Це завершує доведення.

Доведена теорема дуже важлива для знаходження компонент сильної зв'язності. Вона означає, що будь-яке ребро в графі конденсації йде з компоненти з більшим значенням $t_\text{out}$ до компоненти з меншим значенням.

Якщо відсортувати всі вершини $v \in V$ за спаданням їхнього часу виходу $t_\text{out}[v]$, то перша вершина $u$ належатиме «кореневій» компоненті сильної зв'язності, яка не має вхідних ребер у графі конденсації. Тепер ми хочемо запустити з цієї вершини $u$ якийсь різновид пошуку так, щоб він відвідав усі вершини її компоненти сильної зв'язності, але не інші вершини. Повторюючи це, ми зможемо поступово знайти всі компоненти сильної зв'язності: видаляємо всі вершини, що належать першій знайденій компоненті, потім знаходимо наступну з решти вершин з найбільшим значенням $t_\text{out}$, запускаємо з неї цей пошук і так далі. Урешті ми знайдемо всі компоненти сильної зв'язності. Щоб знайти метод пошуку, який поводиться так, як нам потрібно, розгляньмо таку теорему:

Теорема

Нехай $G^T$ позначає транспонований граф графа $G$, отриманий обертанням напрямків ребер у $G$. Тоді $\text{SCC}(G)=\text{SCC}(G^T)$. Крім того, граф конденсації графа $G^T$ є транспонованим до графа конденсації графа $G$.

Доведення опускаємо (воно прямолінійне). Як наслідок цієї теореми, у графі конденсації графа $G^T$ не буде ребер з «кореневої» компоненти до інших компонент. Отже, щоб відвідати всю «кореневу» компоненту сильної зв'язності, яка містить вершину $v$, достатньо запустити пошук у глибину з вершини $v$ у транспонованому графі $G^T$! Це відвідає рівно всі вершини цієї компоненти сильної зв'язності. Як було згадано раніше, потім ми можемо видалити ці вершини з графа. Далі знаходимо наступну вершину з максимальним значенням $t_\text{out}[v]$ і запускаємо пошук у транспонованому графі з цієї вершини, щоб знайти наступну компоненту сильної зв'язності. Повторюючи це, ми знаходимо всі компоненти сильної зв'язності.

Отже, підсумовуючи, ми розглянули такий алгоритм для знаходження компонент сильної зв'язності:

• Крок 1. Запускаємо послідовність пошуків у глибину на $G$, що дасть деякий список (наприклад, order) вершин, відсортований за зростанням часу виходу $t_\text{out}$.

• Крок 2. Будуємо транспонований граф $G^T$ і запускаємо серію пошуків у глибину на вершинах у зворотному порядку (тобто за спаданням часів виходу). Кожен пошук у глибину дасть одну компоненту сильної зв'язності.

• Крок 3 (необов'язковий). Будуємо граф конденсації.

Часова складність алгоритму становить $O(n + m)$, оскільки пошук у глибину виконується двічі. Побудова графа конденсації також має складність $O(n+m).$

Нарешті, доречно тут згадати топологічне сортування. На кроці 1 ми знаходимо вершини в порядку зростання часу виходу. Якщо $G$ ациклічний, це відповідає (оберненому) топологічному сортуванню $G$. На кроці 2 алгоритм знаходить компоненти сильної зв'язності за спаданням їхніх часів виходу. Тобто він знаходить компоненти — вершини графа конденсації — у порядку, що відповідає топологічному сортуванню графа конденсації.

Реалізація

C++

vector<bool> visited; // відстежує, які вершини вже відвідано

// запускає пошук у глибину, починаючи з вершини v.
// кожну відвідану вершину додаємо до вихідного вектора, коли dfs її залишає.
void dfs(int v, vector<vector<int>> const& adj, vector<int> &output) {
    visited[v] = true;
    for (auto u : adj[v])
        if (!visited[u])
            dfs(u, adj, output);
    output.push_back(v);
}

// вхід: adj -- список суміжності G
// вихід: components -- компоненти сильної зв'язності в G
// вихід: adj_cond -- список суміжності G^SCC (за кореневими вершинами)
void strongly_connected_components(vector<vector<int>> const& adj,
                                  vector<vector<int>> &components,
                                  vector<vector<int>> &adj_cond) {
    int n = adj.size();
    components.clear(), adj_cond.clear();

    vector<int> order; // буде відсортованим за часом виходу списком вершин G

    visited.assign(n, false);

    // перша серія пошуків у глибину
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs(i, adj, order);

    // створюємо список суміжності G^T
    vector<vector<int>> adj_rev(n);
    for (int v = 0; v < n; v++)
        for (int u : adj[v])
            adj_rev[u].push_back(v);

    visited.assign(n, false);
    reverse(order.begin(), order.end());

    vector<int> roots(n, 0); // дає кореневу вершину SCC, до якої належить вершина

    // друга серія пошуків у глибину
    for (auto v : order)
        if (!visited[v]) {
            std::vector<int> component;
            dfs(v, adj_rev, component);
            components.push_back(component);
            int root = *component.begin();
            for (auto u : component)
                roots[u] = root;
        }

    // додаємо ребра до графа конденсації
    adj_cond.assign(n, {});
    for (int v = 0; v < n; v++)
        for (auto u : adj[v])
            if (roots[v] != roots[u])
                adj_cond[roots[v]].push_back(roots[u]);
}

Python

import sys

# Збільшуємо ліміт рекурсії, бо глибина DFS може сягати n
# (наприклад, для графа у вигляді ланцюга вершин).
sys.setrecursionlimit(1 << 20)

visited: list[bool] = []  # відстежує, які вершини вже відвідано


# запускає пошук у глибину, починаючи з вершини v.
# кожну відвідану вершину додаємо до вихідного списку, коли dfs її залишає.
def dfs(v: int, adj: list[list[int]], output: list[int]) -> None:
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs(u, adj, output)
    output.append(v)


# вхід: adj -- список суміжності G
# повертає: (components, adj_cond)
#   components -- компоненти сильної зв'язності в G
#   adj_cond  -- список суміжності G^SCC (за кореневими вершинами)
def strongly_connected_components(
    adj: list[list[int]],
) -> tuple[list[list[int]], list[list[int]]]:
    global visited
    n = len(adj)
    components: list[list[int]] = []

    order: list[int] = []  # буде відсортованим за часом виходу списком вершин G

    visited = [False] * n

    # перша серія пошуків у глибину
    for i in range(n):
        if not visited[i]:
            dfs(i, adj, order)

    # створюємо список суміжності G^T
    adj_rev: list[list[int]] = [[] for _ in range(n)]
    for v in range(n):
        for u in adj[v]:
            adj_rev[u].append(v)

    visited = [False] * n
    order.reverse()

    roots = [0] * n  # дає кореневу вершину SCC, до якої належить вершина

    # друга серія пошуків у глибину
    for v in order:
        if not visited[v]:
            component: list[int] = []
            dfs(v, adj_rev, component)
            components.append(component)
            root = component[0]
            for u in component:
                roots[u] = root

    # додаємо ребра до графа конденсації
    adj_cond: list[list[int]] = [[] for _ in range(n)]
    for v in range(n):
        for u in adj[v]:
            if roots[v] != roots[u]:
                adj_cond[roots[v]].append(roots[u])

    return components, adj_cond

TypeScript

let visited: boolean[] = []; // відстежує, які вершини вже відвідано

// запускає пошук у глибину, починаючи з вершини v.
// кожну відвідану вершину додаємо до вихідного масиву, коли dfs її залишає.
function dfs(v: number, adj: number[][], output: number[]): void {
    visited[v] = true;
    for (const u of adj[v])
        if (!visited[u])
            dfs(u, adj, output);
    output.push(v);
}

// вхід: adj -- список суміжності G
// повертає: [components, adjCond]
//   components -- компоненти сильної зв'язності в G
//   adjCond   -- список суміжності G^SCC (за кореневими вершинами)
function stronglyConnectedComponents(
    adj: number[][],
): [number[][], number[][]] {
    const n = adj.length;
    const components: number[][] = [];

    const order: number[] = []; // буде відсортованим за часом виходу списком вершин G

    visited = new Array<boolean>(n).fill(false);

    // перша серія пошуків у глибину
    for (let i = 0; i < n; i++)
        if (!visited[i])
            dfs(i, adj, order);

    // створюємо список суміжності G^T
    const adjRev: number[][] = Array.from({ length: n }, () => []);
    for (let v = 0; v < n; v++)
        for (const u of adj[v])
            adjRev[u].push(v);

    visited = new Array<boolean>(n).fill(false);
    order.reverse();

    const roots = new Array<number>(n).fill(0); // дає кореневу вершину SCC, до якої належить вершина

    // друга серія пошуків у глибину
    for (const v of order)
        if (!visited[v]) {
            const component: number[] = [];
            dfs(v, adjRev, component);
            components.push(component);
            const root = component[0];
            for (const u of component)
                roots[u] = root;
        }

    // додаємо ребра до графа конденсації
    const adjCond: number[][] = Array.from({ length: n }, () => []);
    for (let v = 0; v < n; v++)
        for (const u of adj[v])
            if (roots[v] !== roots[u])
                adjCond[roots[v]].push(roots[u]);

    return [components, adjCond];
}

Go

var visited []bool // відстежує, які вершини вже відвідано

// запускає пошук у глибину, починаючи з вершини v.
// кожну відвідану вершину додаємо до вихідного зрізу, коли dfs її залишає.
func dfs(v int, adj [][]int, output *[]int) {
    visited[v] = true
    for _, u := range adj[v] {
        if !visited[u] {
            dfs(u, adj, output)
        }
    }
    *output = append(*output, v)
}

// вхід: adj -- список суміжності G
// повертає: components -- компоненти сильної зв'язності в G
// повертає: adjCond -- список суміжності G^SCC (за кореневими вершинами)
func stronglyConnectedComponents(adj [][]int) (components, adjCond [][]int) {
    n := len(adj)

    order := []int{} // буде відсортованим за часом виходу списком вершин G

    visited = make([]bool, n)

    // перша серія пошуків у глибину
    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i, adj, &order)
        }
    }

    // створюємо список суміжності G^T
    adjRev := make([][]int, n)
    for v := 0; v < n; v++ {
        for _, u := range adj[v] {
            adjRev[u] = append(adjRev[u], v)
        }
    }

    visited = make([]bool, n)
    for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
        order[i], order[j] = order[j], order[i]
    }

    roots := make([]int, n) // дає кореневу вершину SCC, до якої належить вершина

    // друга серія пошуків у глибину
    for _, v := range order {
        if !visited[v] {
            component := []int{}
            dfs(v, adjRev, &component)
            components = append(components, component)
            root := component[0]
            for _, u := range component {
                roots[u] = root
            }
        }
    }

    // додаємо ребра до графа конденсації
    adjCond = make([][]int, n)
    for v := 0; v < n; v++ {
        for _, u := range adj[v] {
            if roots[v] != roots[u] {
                adjCond[roots[v]] = append(adjCond[roots[v]], roots[u])
            }
        }
    }

    return components, adjCond
}

Функція dfs реалізує пошук у глибину. На вхід вона приймає список суміжності та початкову вершину. Вона також приймає посилання на вектор output: кожну відвідану вершину буде додано до output, коли dfs залишає цю вершину.

Зауважте, що ми використовуємо функцію dfs як на першому, так і на другому кроці алгоритму. На першому кроці ми передаємо список суміжності $G$, і впродовж послідовних викликів dfs ми передаємо той самий «вихідний вектор» order, тож зрештою отримуємо список вершин у порядку зростання часів виходу. На другому кроці ми передаємо список суміжності $G^T$, і в кожному виклику передаємо порожній «вихідний вектор» component, який даватиме нам по одній компоненті сильної зв'язності за раз.

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

Опис алгоритму

Описаний алгоритм уперше запропонував Тар'ян у 1972 році. Він ґрунтується на виконанні послідовності викликів DFS і використовує інформацію, властиву самій його структурі, щоб визначити компоненти сильної зв'язності (SCC), маючи час роботи $O(n+m)$.

Застосовуючи DFS до вершини, ми обходимо її список суміжності, і якщо знаходимо вершину, яку ще не відвідано, рекурсивно застосовуємо до неї DFS.

Розгляньмо дерево, породжене послідовністю викликів DFS, яке ми називатимемо деревом DFS. Щойно ми вперше викликаємо DFS на вершині з якоїсь SCC, усі вершини цієї SCC буде відвідано до завершення цього виклику, оскільки всі вони досяжні одна з одної. У дереві DFS ця перша вершина буде спільним предком усіх інших вершин SCC; цю вершину ми означаємо як корінь SCC.

Теорема

Усі вершини SCC породжують зв'язний підграф дерева DFS.

Доведення

Ми встановили, що всі вершини SCC мають спільного предка — першу вершину, яку відвідав виклик DFS. Розгляньмо вершину $v$ та її корінь — вершину $r$. Усі вершини на шляху з $r$ до $v$ належать тій самій SCC. Усі ці вершини досяжні з $r$, і всі вони досягають $v$, а оскільки за означенням $v$ досягає $r$, то всі ці вершини досягають одна одної. Оскільки всі шляхи з кореня до кожної іншої вершини SCC належать тій самій SCC, утворений підграф є зв'язним.

Зауважте, що SCC ідеально розбивають дерево DFS на зв'язні підграфи.

Тоді ідея алгоритму така:

• Ми виконуємо послідовність викликів DFS, рекурсивно застосовуючи їх до вершин зі списків суміжності.

• Щойно ми завершуємо обхід списку суміжності вершини, ми якимось чином можемо визначити, чи є вона коренем. Цей метод буде пояснено пізніше.

• Якщо вершина є коренем, ми одразу знаходимо й привласнюємо всі вершини її SCC.

Коли всі виклики завершуються, усі корені буде виявлено, і всі вершини буде привласнено до якоїсь SCC.

Тепер проаналізуймо властивості DFS, коли вводиться цей процес привласнення.

Теорема

Розгляньмо вершину $v$ і нехай ми щойно завершили обхід її списку суміжності. Усі непривласнені вершини в її піддереві належать тій самій SCC.

Доведення

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

Теорема

Розгляньмо вершину $v$ і нехай ми обходимо її список суміжності, наразі обробляючи ребро $(v, u)$. Якщо $u$ вже було відвідано якимось викликом DFS і вона лишається непривласненою, то $v$ і $u$ належать тій самій SCC.

Доведення

Маємо різні випадки залежно від виду ребра:

• Деревне ребро (tree-edge): якщо це деревне ребро, то ми вперше знаходимо вершину $u$. Це означає, що ми спершу маємо рекурсивно застосувати виклик DFS до $u$ і розглянути її після завершення її виклику DFS. Якщо вершина $u$ лишається непривласненою, то її корінь — це або $v$, або предок $v$, тож вони мають належати тій самій SCC.

• Зворотне ребро (back-edge): це простіший випадок; якщо $u$ є предком $v$, то вони досяжні одна з одної і за означенням належать тій самій SCC.

• Пряме ребро (forward-edge): перш ніж це ребро було оброблено, була послідовність викликів DFS, яка завершилася, не знайшовши кореня $u$, повернувшись до $v$, чий виклик DFS продовжився. Тоді коренем $u$ буде предок, процес привласнення якого ще не виконувався, тож це або $v$, або предок $v$, отже, вони мають належати тій самій SCC.

• Перехресне ребро (cross-edge): аналогічно, перш ніж це ребро було оброблено, була послідовність викликів DFS, яка завершилася, не знайшовши кореня $u$, повернувшись до спільного предка $u$ і $v$, чий виклик DFS продовжився та започаткував нову послідовність викликів DFS, що привела до виклику на $v$. Тоді коренем $u$ буде предок, процес привласнення якого ще не виконувався, і всі можливі кандидати є спільними предками з $v$. Оскільки корінь $u$ є предком $v$, він досягає $v$, а оскільки $v$ тепер досягає $u$, то вони мають належати тій самій SCC.

Зауважте: коли дві вершини належать одній компоненті, їхній корінь має бути спільним предком обох вершин.

Теорема

Нехай $v$ — вершина. Наступні твердження рівносильні:

1. Деяка вершина в піддереві $v$ досягає непривласненої вершини поза піддеревом.
2. $v$ не є коренем SCC.

Доведення

• $1. \implies 2.$: Припустимо, що деяка вершина $u$ в піддереві $v$ досягає непривласненої вершини $w$ поза піддеревом. Ми встановили, що $u$ і $w$ належать тій самій SCC і що їхній корінь має бути спільним предком обох. Цей спільний предок обов'язково лежить поза піддеревом, і він також буде предком $v$. Оскільки $v$ лежить на шляху від кореня до $u$, вона має належати тій самій SCC, коренем якої не є $v$.

• $\neg 1. \implies \neg 2.$: Припустимо, що жодна вершина в піддереві $v$ не досягає непривласненої вершини поза піддеревом. Це має означати, що жодна вершина в піддереві $v$ не досягає предка $v$. Єдині можливі ребра до вершин поза піддеревом — це перехресні ребра до вершин, які вже привласнено; ці вершини не можуть досягати предка $v$, бо якби могли, то належали б тій самій SCC, що й $v$, що неможливо, оскільки їхню SCC вже визначено. Оскільки жоден предок $v$ не досяжний з її піддерева, коренем $v$ має бути сама $v$.

Тепер ми маємо знайти метод, який дозволить нам визначити, чи є вершина коренем, і властивості процесу привласнення необхідні для його коректності. Із цією метою ми означаємо час входу $t_{in}[v]$ для кожної вершини $v \in G$, який відповідає «мітці часу», у яку було викликано DFS на $v$. За означенням корінь є першою вершиною SCC, яку відвідує DFS, тож він матиме мінімальне значення $t_{in}$ серед своєї SCC.

Нехай $v$ — вершина, і розгляньмо її піддерево. У момент, коли ми завершуємо обхід її списку суміжності, будь-яка вершина, уже відвідана DFS поза піддеревом, матиме менше значення $t_{in}$, оскільки DFS було викликано на ній раніше, ніж він почався на $v$.

Якщо врахувати процес привласнення, значення $t_{in}$ усіх непривласнених вершин поза піддеревом $v$ менше за $t_{in}[v]$. Тепер ми можемо побачити, як використати $t_{in}$ для визначення коренів. Ми розглядаємо мінімальне значення $t_{in}$ серед непривласнених вершин, яких можемо досягти, і поширюємо цю інформацію до предків через деревні ребра. Поширене значення ми називатимемо $t_{low}$.

Формальніше, ми означаємо $t_{low}[v]$ як найменше значення $t_{in}$, якого вершина в піддереві $v$ може досягти через пряме ребро. Тому ми можемо виявити, чи є вершина $v$ коренем, перевіривши, чи $t_{low}[v] < t_{in}[v]$.

Нарешті, щоб привласнити вершини, є багато способів це зробити, наприклад інший алгоритм обходу графа, але можна також використати просту структуру даних для відстеження непривласнених вершин. Щоб визначити цю структуру даних із перших принципів, перегляньмо методи, які вона має реалізувати, — їх лише два:

• Коли ми вперше відвідуємо вершину, ми просто вставляємо її в структуру даних, оскільки ця вершина непривласнена.

• Коли ми знаходимо корінь, ми маємо знайти всі решта непривласнених вершин у його піддереві й видалити їх зі структури даних.

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

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

Тепер бачимо, що це можна реалізувати за допомогою стеку:

• Коли ми вперше відвідуємо вершину, ми кладемо її на стек.

• Коли ми знаходимо корінь, ми знімаємо зі стеку всі елементи, доки не знімемо сам корінь.

Це нарешті дозволяє нам реалізувати алгоритм.

Часова складність послідовності викликів DFS становить $O(n + m)$. Якщо врахувати стек, його складність амортизується до $O(n)$, оскільки кожен вузол лише раз кладуть і раз знімають. Тому загальна часова складність становить $O(n + m)$.

Як додаткове зауваження, корені знаходяться в оберненому топологічному порядку. В алгоритмі вершина є коренем, якщо немає ребер до непривласнених вершин поза її піддеревом, тобто всі інші досяжні компоненти або лежать у її піддереві (а отже, їхні корені вже було знайдено), або з'єднуються з уже привласненими вершинами поза піддеревом (чиї корені також уже було знайдено). Тож усі досяжні компоненти вже було знайдено, тобто вони вводяться у коректному оберненому топологічному порядку графа конденсації.

Реалізація

C++

vector<int> st;    // - стек, що містить непривласнені вершини
vector<int> roots; // - відстежує корені SCC для вершин
int timer;         // - лічильник міток часу dfs
vector<int> t_in;  // - відстежує мітку часу dfs для вершин
vector<int> t_low; // - відстежує найменше t_in непривласнених вершин,
                   // досяжних у піддереві

// реалізує алгоритм Тар'яна для компонент сильної зв'язності
void dfs(int v, vector<vector<int>> const &adj, vector<vector<int>> &components) {

  t_low[v] = t_in[v] = timer++;
  st.push_back(v);

  for (auto u : adj[v]) {
    if (t_in[u] == -1) { // деревне ребро
      dfs(u, adj, components);
      t_low[v] = min(t_low[v], t_low[u]);
    } else if (roots[u] == -1) { // зворотне, перехресне або пряме ребро до непривласненої вершини
      t_low[v] = min(t_low[v], t_in[u]);
    }
  }

  if (t_low[v] == t_in[v]) { // вершина є коренем
    components.push_back({v}); // ініціалізує нову компоненту з коренем v
    while (true) {
      int u = st.back();
      st.pop_back();
      roots[u] = v; // привласнює вершину
      if (u == v)
        break;
      components.back().push_back(u); // додає вершину u до компоненти v
    }
  }
}

// вхід: adj -- список суміжності G
// вихід: components -- компоненти сильної зв'язності в G
// вихід: adj_cond -- список суміжності G^SCC (за кореневими вершинами)
void strongly_connected_components(vector<vector<int>> const &adj,
                                   vector<vector<int>> &components,
                                   vector<vector<int>> &adj_cond) {
  components.clear();
  adj_cond.clear();

  int n = adj.size();

  st.clear();
  roots.assign(n, -1);
  timer = 0;
  t_in.assign(n, -1);
  t_low.assign(n, -1);

  // застосовує алгоритм Тар'яна до всіх вершин
  // додає вершини до компонент в оберненому топологічному порядку
  for (int v = 0; v < n; v++) {
    if (t_in[v] == -1) {
      dfs(v, adj, components);
    }
  }

  // додає ребра до графа конденсації
  adj_cond.assign(n, {});
  for (int v = 0; v < n; v++) {
    for (auto u : adj[v])
      if (roots[v] != roots[u])
        adj_cond[roots[v]].push_back(roots[u]);
  }
}

Python

import sys

# Збільшуємо ліміт рекурсії, бо глибина DFS може сягати n
# (наприклад, для графа у вигляді ланцюга вершин).
sys.setrecursionlimit(1 << 20)

st: list[int] = []     # - стек, що містить непривласнені вершини
roots: list[int] = []  # - відстежує корені SCC для вершин
timer: int = 0         # - лічильник міток часу dfs
t_in: list[int] = []   # - відстежує мітку часу dfs для вершин
t_low: list[int] = []  # - відстежує найменше t_in непривласнених вершин,
                       #   досяжних у піддереві


# реалізує алгоритм Тар'яна для компонент сильної зв'язності
def dfs(v: int, adj: list[list[int]], components: list[list[int]]) -> None:
    global timer
    t_low[v] = t_in[v] = timer
    timer += 1
    st.append(v)

    for u in adj[v]:
        if t_in[u] == -1:  # деревне ребро
            dfs(u, adj, components)
            t_low[v] = min(t_low[v], t_low[u])
        elif roots[u] == -1:  # зворотне, перехресне або пряме ребро до непривласненої вершини
            t_low[v] = min(t_low[v], t_in[u])

    if t_low[v] == t_in[v]:  # вершина є коренем
        components.append([v])  # ініціалізує нову компоненту з коренем v
        while True:
            u = st.pop()
            roots[u] = v  # привласнює вершину
            if u == v:
                break
            components[-1].append(u)  # додає вершину u до компоненти v


# вхід: adj -- список суміжності G
# повертає: (components, adj_cond)
#   components -- компоненти сильної зв'язності в G
#   adj_cond  -- список суміжності G^SCC (за кореневими вершинами)
def strongly_connected_components(
    adj: list[list[int]],
) -> tuple[list[list[int]], list[list[int]]]:
    global st, roots, timer, t_in, t_low
    components: list[list[int]] = []

    n = len(adj)

    st = []
    roots = [-1] * n
    timer = 0
    t_in = [-1] * n
    t_low = [-1] * n

    # застосовує алгоритм Тар'яна до всіх вершин
    # додає вершини до компонент в оберненому топологічному порядку
    for v in range(n):
        if t_in[v] == -1:
            dfs(v, adj, components)

    # додає ребра до графа конденсації
    adj_cond: list[list[int]] = [[] for _ in range(n)]
    for v in range(n):
        for u in adj[v]:
            if roots[v] != roots[u]:
                adj_cond[roots[v]].append(roots[u])

    return components, adj_cond

TypeScript

let st: number[] = [];     // - стек, що містить непривласнені вершини
let roots: number[] = [];  // - відстежує корені SCC для вершин
let timer: number = 0;     // - лічильник міток часу dfs
let tIn: number[] = [];    // - відстежує мітку часу dfs для вершин
let tLow: number[] = [];   // - відстежує найменше t_in непривласнених вершин,
                           //   досяжних у піддереві

// реалізує алгоритм Тар'яна для компонент сильної зв'язності
function dfs(v: number, adj: number[][], components: number[][]): void {
    tLow[v] = tIn[v] = timer++;
    st.push(v);

    for (const u of adj[v]) {
        if (tIn[u] === -1) { // деревне ребро
            dfs(u, adj, components);
            tLow[v] = Math.min(tLow[v], tLow[u]);
        } else if (roots[u] === -1) { // зворотне, перехресне або пряме ребро до непривласненої вершини
            tLow[v] = Math.min(tLow[v], tIn[u]);
        }
    }

    if (tLow[v] === tIn[v]) { // вершина є коренем
        components.push([v]); // ініціалізує нову компоненту з коренем v
        while (true) {
            const u = st.pop()!;
            roots[u] = v; // привласнює вершину
            if (u === v)
                break;
            components[components.length - 1].push(u); // додає вершину u до компоненти v
        }
    }
}

// вхід: adj -- список суміжності G
// повертає: [components, adjCond]
//   components -- компоненти сильної зв'язності в G
//   adjCond   -- список суміжності G^SCC (за кореневими вершинами)
function stronglyConnectedComponents(
    adj: number[][],
): [number[][], number[][]] {
    const components: number[][] = [];

    const n = adj.length;

    st = [];
    roots = new Array<number>(n).fill(-1);
    timer = 0;
    tIn = new Array<number>(n).fill(-1);
    tLow = new Array<number>(n).fill(-1);

    // застосовує алгоритм Тар'яна до всіх вершин
    // додає вершини до компонент в оберненому топологічному порядку
    for (let v = 0; v < n; v++) {
        if (tIn[v] === -1) {
            dfs(v, adj, components);
        }
    }

    // додає ребра до графа конденсації
    const adjCond: number[][] = Array.from({ length: n }, () => []);
    for (let v = 0; v < n; v++) {
        for (const u of adj[v])
            if (roots[v] !== roots[u])
                adjCond[roots[v]].push(roots[u]);
    }

    return [components, adjCond];
}

Go

var (
    st    []int // - стек, що містить непривласнені вершини
    roots []int // - відстежує корені SCC для вершин
    timer int   // - лічильник міток часу dfs
    tIn   []int // - відстежує мітку часу dfs для вершин
    tLow  []int // - відстежує найменше t_in непривласнених вершин, досяжних у піддереві
)

// реалізує алгоритм Тар'яна для компонент сильної зв'язності
func dfs(v int, adj [][]int, components *[][]int) {
    tIn[v] = timer
    tLow[v] = timer
    timer++
    st = append(st, v)

    for _, u := range adj[v] {
        if tIn[u] == -1 { // деревне ребро
            dfs(u, adj, components)
            tLow[v] = min(tLow[v], tLow[u])
        } else if roots[u] == -1 { // зворотне, перехресне або пряме ребро до непривласненої вершини
            tLow[v] = min(tLow[v], tIn[u])
        }
    }

    if tLow[v] == tIn[v] { // вершина є коренем
        *components = append(*components, []int{v}) // ініціалізує нову компоненту з коренем v
        for {
            u := st[len(st)-1]
            st = st[:len(st)-1]
            roots[u] = v // привласнює вершину
            if u == v {
                break
            }
            last := len(*components) - 1
            (*components)[last] = append((*components)[last], u) // додає вершину u до компоненти v
        }
    }
}

// вхід: adj -- список суміжності G
// повертає: components -- компоненти сильної зв'язності в G
// повертає: adjCond -- список суміжності G^SCC (за кореневими вершинами)
func stronglyConnectedComponents(adj [][]int) (components, adjCond [][]int) {
    n := len(adj)

    st = nil
    roots = make([]int, n)
    timer = 0
    tIn = make([]int, n)
    tLow = make([]int, n)
    for i := 0; i < n; i++ {
        roots[i] = -1
        tIn[i] = -1
        tLow[i] = -1
    }

    // застосовує алгоритм Тар'яна до всіх вершин
    // додає вершини до компонент в оберненому топологічному порядку
    for v := 0; v < n; v++ {
        if tIn[v] == -1 {
            dfs(v, adj, &components)
        }
    }

    // додає ребра до графа конденсації
    adjCond = make([][]int, n)
    for v := 0; v < n; v++ {
        for _, u := range adj[v] {
            if roots[v] != roots[u] {
                adjCond[roots[v]] = append(adjCond[roots[v]], roots[u])
            }
        }
    }

    return components, adjCond
}

Ми маємо прийняте розв'язання з цим кодом у Library Checker.

Як останнє зауваження, є альтернативний спосіб ітерувати списком суміжності. Наразі ми робимо так:

C++

for (auto u : adj[v]) {
  if (t_in[u] == -1) { // деревне ребро
    dfs(u, adj);
    t_low[v] = min(t_low[v], t_low[u]);
  } else if (roots[u] == -1) { // зворотне, перехресне або пряме ребро до непривласненої вершини
    t_low[v] = min(t_low[v], t_in[u]);
  }
}

Python

for u in adj[v]:
    if t_in[u] == -1:  # деревне ребро
        dfs(u, adj)
        t_low[v] = min(t_low[v], t_low[u])
    elif roots[u] == -1:  # зворотне, перехресне або пряме ребро до непривласненої вершини
        t_low[v] = min(t_low[v], t_in[u])

TypeScript

for (const u of adj[v]) {
  if (tIn[u] === -1) { // деревне ребро
    dfs(u, adj);
    tLow[v] = Math.min(tLow[v], tLow[u]);
  } else if (roots[u] === -1) { // зворотне, перехресне або пряме ребро до непривласненої вершини
    tLow[v] = Math.min(tLow[v], tIn[u]);
  }
}

Go

for _, u := range adj[v] {
    if tIn[u] == -1 { // деревне ребро
        dfs(u, adj)
        tLow[v] = min(tLow[v], tLow[u])
    } else if roots[u] == -1 { // зворотне, перехресне або пряме ребро до непривласненої вершини
        tLow[v] = min(tLow[v], tIn[u])
    }
}

Натомість можна зробити так:

C++

for (auto u : adj[v]) {
  if (t_in[u] == -1) // вершину не відвідано
    dfs(u, adj);
  if (roots[u] == -1) // вершину не привласнено
    t_low[v] = min(t_low[v], t_low[u]);
}

Python

for u in adj[v]:
    if t_in[u] == -1:  # вершину не відвідано
        dfs(u, adj)
    if roots[u] == -1:  # вершину не привласнено
        t_low[v] = min(t_low[v], t_low[u])

TypeScript

for (const u of adj[v]) {
  if (tIn[u] === -1) // вершину не відвідано
    dfs(u, adj);
  if (roots[u] === -1) // вершину не привласнено
    tLow[v] = Math.min(tLow[v], tLow[u]);
}

Go

for _, u := range adj[v] {
    if tIn[u] == -1 { // вершину не відвідано
        dfs(u, adj)
    }
    if roots[u] == -1 { // вершину не привласнено
        tLow[v] = min(tLow[v], tLow[u])
    }
}

$t_{low}$ використовується для поширення інформації до кореня, і коли ми виконуємо t_low[v] = min(t_low[v], t_in[u]), ми знаємо, що $u$ і $v$ належать тій самій SCC. Якщо $t_{low}[u]$ поширюється аж до кореня $u$, то його також можна поширити через $v$, оскільки корінь той самий. Оскільки $t_{low}[u] \leq t_{in}[u]$, це не вносить жодних конфліктів, а лише покращує оцінку на корінь $v$.

Побудова графа конденсації

Будуючи список суміжності графа конденсації, ми обираємо корінь кожної компоненти як першу вершину в її списку вершин (це довільний вибір). Ця коренева вершина представляє всю свою SCC. Для кожної вершини v значення roots[v] вказує кореневу вершину SCC, до якої належить v.

Наш граф конденсації тепер задається вершинами components (одна компонента сильної зв'язності відповідає одній вершині графа конденсації), а список суміжності задається adj_cond, де використовуються лише кореневі вершини компонент сильної зв'язності. Зауважте, що ми породжуємо одне ребро з $C$ до $C'$ у $G^\text{SCC}$ для кожного ребра з деякої $a\in C$ до деякої $b\in C'$ у $G$ (якщо $C\neq C'$). Це означає, що в нашій реалізації між двома компонентами графа конденсації може бути кілька ребер.

Література

• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005].
• M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979].
• Robert Tarjan. Depth-first search and linear graph algorithms [1972].

Задачі для практики

• SPOJ - Good Travels
• SPOJ - Lego
• Codechef - Chef and Round Run
• UVA - 11838 - Come and Go
• UVA 247 - Calling Circles
• UVA 13057 - Prove Them All
• UVA 12645 - Water Supply
• UVA 11770 - Lighting Away
• UVA 12926 - Trouble in Terrorist Town
• UVA 11324 - The Largest Clique
• UVA 11709 - Trust groups
• UVA 12745 - Wishmaster
• SPOJ - True Friends
• SPOJ - Capital City
• Codeforces - Scheme
• SPOJ - Ada and Panels
• CSES - Flight Routes Check
• CSES - Planets and Kingdoms
• CSES - Coin Collector
• Codeforces - Checkposts

Відеоматеріали