E028. Поиск компонент сильной связности, построение конденсации 图а

Источник: e-maxx.ru/algo, страница PDF 89.

Определения, постановка задачи

Дан ориентированный 图

, множество вершин которого

и множество рёбер —

. Петли и кратные

рёбра допускаются. Обозначим через

количество вершин 图а, через

— количество рёбер. Компонентой сильной связности (strongly connected component) называется такое (максимальное

по включению) подмножество вершин

, что любые две вершины этого подмножества достижимы друг из друга, т.е.

для

:

где символом

здесь и далее мы будем обозначать достижимость, т.е. существование пути из первой вершины во вторую. Понятно, что компоненты сильной связности для данного 图а не пересекаются, т.е. фактически это разбиение

всех вершин 图а. Отсюда логично 定义 конденсации

как 图а, получаемого из данного

图а сжатием каждой компоненты сильной связности в одну вершину. Каждой вершине 图а конденсации

соответствует компонента сильной связности 图а

, а ориентированное edge между двумя vertexми

и

图а конденсации проводится, если найдётся пара вершин

, между которыми существовало edge

в исходном 图е, т.е. . Важнейшим свойством 图а конденсации является то, что он ацикличен. Действительно, предположим,

что

, докажем, что

. Из определения конденсации получаем, что найдутся две вершины

и

, что

. Доказывать будем от противного, т.е. предположим, что

, тогда найдутся две

вершины

и

, что

. Но т.к.

и

находятся в одной компоненте сильной связности, то

между ними есть путь; аналогично для

и

. В итоге, объединяя пути, получаем, что

, и одновременно

. Следовательно,

и

должны принадлежать одной компоненте сильной связности, т.е. получили противоречие, что и требовалось доказать. Описываемый ниже 算法 выделяет в данном 图е все компоненты сильной связности. Построить по ним 图 конденсации не составит труда.

算法

Описываемый здесь 算法 был предложен независимо Косараю (Kosaraju) и Шариром (Sharir) в 1979 г. Это очень простой в реализации 算法, основанный на двух сериях поисков в глубину, и потому работающий за

время

. На первом шаге 算法а выполняется серия обходов в глубину, посещающая весь 图. Для этого мы проходимся по всем vertexм 图а и из каждой ещё не посещённой вершины вызываем обход в глубину. При

этом для каждой вершины

запомним время 输出а

. Эти времена 输出а играют ключевую роль

в 算法е, и эта роль выражена в приведённой ниже теореме.

Сначала введём обозначение: время 输出а

из компоненты

сильной связности определим как максимум

из значений

для всех

. Кроме того, в доказательстве теоремы будут упоминаться и времена 输入а

в каждую вершину

, и аналогично определим времена 输入а

для каждой компоненты сильной

связности как минимум из величин

для всех

.

Теорема. Пусть

и

— две различные компоненты сильной связности, и пусть в 图е конденсации между

ними есть edge

. Тогда

. При доказательстве возникает два принципиально различных случая в зависимости от того, в какую из компонент первой зайдёт обход в глубину, т.е. в зависимости от соотношения между

и

:

● Первой была достигнута компонента

. Это означает, что в какой-то момент времени обход в глубину заходит

в некоторую вершину

компоненты

, при этом все остальные вершины компонент

и

ещё не посещены. Но, т.к.

по условию в 图е конденсаций есть edge

, то из вершины

будет достижима не только вся компонента

,

но и вся компонента

. Это означает, что при запуске из вершины

обход в глубину пройдёт по всем

vertexм компонент

и

, а, значит, они станут потомками по отношению к

в дереве обхода в глубину, т.е.

для любой вершины

будет выполнено

, ч.т.д.

● Первой была достигнута компонента

. Опять же, в какой-то момент времени обход в глубину заходит в

некоторую вершину

, причём все остальные вершины компонент

и

не посещены. Поскольку по условию

в 图е конденсаций существовало edge

, то, вследствие ацикличности 图а конденсаций, не

существует обратного пути

, т.е. обход в глубину из вершины

не достигнет вершин

. Это означает, что

они будут посещены обходом в глубину позже, откуда и следует

, ч.т.д. Доказанная теорема является основой 算法а поиска компонент сильной связности. Из неё следует,

что любое edge

в 图е конденсаций идёт из компоненты с большей величиной

в компоненту с

меньшей величиной.

Если мы отсортируем все вершины

в порядке убывания времени 输出а

, то первой окажется

некоторая vertex

, принадлежащая "корневой" компоненте сильной связности, т.е. в которую не 输入ит ни одно edge в 图е конденсаций. Теперь нам хотелось бы запустить такой обход из этой вершины

, который бы посетил только

эту компоненту сильной связности и не зашёл ни в какую другую; научившись это делать, мы сможем постепенно выделить все компоненты сильной связности: удалив из 图а вершины первой выделенной компоненты, мы

снова найдём среди оставшихся вершину с наибольшей величиной

, снова запустим из неё этот обход, и т.д. Чтобы научиться делать такой обход, рассмотрим транспонированный 图

, т.е. 图, полученный из

изменением направления каждого ребра на противоположное. Нетрудно понять, что в этом 图е будут те же компоненты сильной связности, что и в исходном 图е. Более того, 图 конденсации

для него

будет равен транспонированному 图у конденсации исходного 图а

. Это означает, что теперь

из рассматриваемой нами "корневой" компоненты уже не будут 输出ить рёбра в другие компоненты. Таким образом, чтобы обойти всю "корневую" компоненту сильной связности, содержащую некоторую вершину

, достаточно запустить обход из вершины

в 图е

. Этот обход посетит все вершины этой компоненты

сильной связности и только их. Как уже говорилось, дальше мы можем мысленно удалить эти вершины из 图а,

находить очередную вершину с максимальным значением

и запускать обход на транспонированном 图е

из неё, и т.д. Итак, мы построили следующий 算法 выделения компонент сильной связности:

1 шаг. Запустить серию обходов в глубину 图а

, которая returns вершины в порядке увеличения времени

输出а

, т.е. некоторый список

.

2 шаг. Построить транспонированный 图

. Запустить серию обходов в глубину/ширину этого 图а в

порядке, определяемом списком

(а именно, в обратном порядке, т.е. в порядке уменьшения времени 输出а). Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Asymptotic complexity 算法а, очевидно, равна

, поскольку он представляет собой всего лишь два обхода

в глубину/ширину. Наконец, уместно отметить связь с понятием топологической сортировки. Во-первых, шаг 1 算法а представляет собой не что иное, как топологическую сортировку 图а

(фактически именно это и

означает сортировка вершин по времени 输出а). Во-вторых, сама схема 算法а такова, что и компоненты сильной связности он генерирует в порядке уменьшения их времён 输出а, таким образом, он генерирует компоненты - вершины 图а конденсации в порядке топологической сортировки.

实现

vector < vector<int> > g, gr;

vector<char> used;

vector<int> order, component;

void dfs1 (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i)

if (!used[ g[v][i] ])

dfs1 (g[v][i]);

order.push_back (v);

}

void dfs2 (int v) {

used[v] = true;

component.push_back (v);

for (size_t i=0; i<gr[v].size(); ++i)

if (!used[ gr[v][i] ])

dfs2 (gr[v][i]);

}

int main() {

int n;

... чтение n ...

for (;;) {

int a, b;

... чтение очередного ребра (a,b) ...

g[a].push_back (b);

gr[b].push_back (a);

}

used.assign (n, false);

for (int i=0; i<n; ++i)

if (!used[i])

dfs1 (i);

used.assign (n, false);

for (int i=0; i<n; ++i) {

int v = order[n-1-i];

if (!used[v]) {

dfs2 (v);

... вывод очередной component ...

component.clear();

} } }

Здесь в

хранится сам 图, а

— транспонированный 图. Функция

выполняет обход в глубину на 图е

, функция

— на транспонированном

. Функция

заполняет список

vertexми в

порядке увеличения времени 输出а (фактически, делает топологическую сортировку). Функция

сохраняет

все достигнутые вершины в списке

, который после каждого запуска будет содержать

очередную компоненту сильной связности.

References

● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. 算法ы: Построение и

анализ [2005]

● M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    vector < List<int> > g, gr;
    List<char> used;
    List<int> order, component;
    void dfs1 (int v) {
            used[v] = true;
            for (size_t i=0; i<g[v].size(); ++i)
                    if (!used[ g[v][i] ])
                            dfs1 (g[v][i]);
            order.push_back (v);
    }
    void dfs2 (int v) {
            used[v] = true;
            component.push_back (v);
            for (size_t i=0; i<gr[v].size(); ++i)
                    if (!used[ gr[v][i] ])
                            dfs2 (gr[v][i]);
    }
    int main() {
            int n;
            ... чтение n ...
            for (;;) {
                    int a, b;
                    ... чтение очередного ребра (a,b) ...
                    g[a].push_back (b);
                    gr[b].push_back (a);
            }
            used.assign (n, false);
            for (int i=0; i<n; ++i)
                    if (!used[i])
                            dfs1 (i);
            used.assign (n, false);
            for (int i=0; i<n; ++i) {
                    int v = order[n-1-i];
                    if (!used[v]) {
                            dfs2 (v);
                            ... вывод очередной component ...
                            component.clear();
                    }
            }
    }
}

vector < vector<int> > g, gr;
vector<char> used;
vector<int> order, component;
void dfs1 (int v) {
        used[v] = true;
        for (size_t i=0; i<g[v].size(); ++i)
                if (!used[ g[v][i] ])
                        dfs1 (g[v][i]);
        order.push_back (v);
}
void dfs2 (int v) {
        used[v] = true;
        component.push_back (v);
        for (size_t i=0; i<gr[v].size(); ++i)
                if (!used[ gr[v][i] ])
                        dfs2 (gr[v][i]);
}
int main() {
        int n;
        ... чтение n ...
        for (;;) {
                int a, b;
                ... чтение очередного ребра (a,b) ...
                g[a].push_back (b);
                gr[b].push_back (a);
        }
        used.assign (n, false);
        for (int i=0; i<n; ++i)
                if (!used[i])
                        dfs1 (i);
        used.assign (n, false);
        for (int i=0; i<n; ++i) {
                int v = order[n-1-i];
                if (!used[v]) {
                        dfs2 (v);
                        ... вывод очередной component ...
                        component.clear();
                }
        }
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    vector < ArrayList<Integer> > g, gr;
    ArrayList<Character> used;
    ArrayList<Integer> order, component;
    void dfs1 (int v) {
            used[v] = true;
            for (size_t i=0; i<g[v].size(); ++i)
                    if (!used[ g[v][i] ])
                            dfs1 (g[v][i]);
            order.push_back (v);
    }
    void dfs2 (int v) {
            used[v] = true;
            component.push_back (v);
            for (size_t i=0; i<gr[v].size(); ++i)
                    if (!used[ gr[v][i] ])
                            dfs2 (gr[v][i]);
    }
    int main() {
            int n;
            ... чтение n ...
            for (;;) {
                    int a, b;
                    ... чтение очередного ребра (a,b) ...
                    g[a].push_back (b);
                    gr[b].push_back (a);
            }
            used.assign (n, false);
            for (int i=0; i<n; ++i)
                    if (!used[i])
                            dfs1 (i);
            used.assign (n, false);
            for (int i=0; i<n; ++i) {
                    int v = order[n-1-i];
                    if (!used[v]) {
                            dfs2 (v);
                            ... вывод очередной component ...
                            component.clear();
                    }
            }
    }
}