Задача 1. Лекция. Графы. Определения ≡

Условие

Ориентированный граф (directed graph) определяется как пара множеств (V,E), где V — конечное множество, а E — множество всех пар элементов из V, т.е. подмножество множества V × V. Ориентированный граф иногда для краткости называют орграфом (digraph). Множество V называют множеством вершин графа (vertex set); его элемент называют вершиной графа (vertex; множественное число vertices). Множество E называют множеством ребер (edge set) графа; его элементы называют ребрами (edges). На рисунке 1(а) показан ориентированный граф с множеством вершин {1,2,3,4,5,6}. Вершины изображены кружками, а ребра — стрелками. Заметим, что граф может содержать ребра-петли (self-loops), соединяющие вершину с собой.

В неориентированном (undirected) графе G = (V, E) множество ребер E состоит из неупорядоченных (unordered) пар вершин: парами являются множества {u, v}, где u, v ∈ V и u ≠ v. Мы будем обозначать неориентированное ребро как (u, v) вместо {u, v}; при этом для неориентированного графа (u, v) и (v, u) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин. На рисунке 1(б) изображен неориентированный граф с множеством вершин {1,2,3,4,5,6}.

Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (u, v) ориентированного графа говорят, что оно выходит из (incident from, leaves) вершины u и входит в (incident to, enters) вершину v. Например, на рис. 1(а) имеется три ребра, выходящих из вершины 2 ((2,2), (2,4), (2,5)) и два ребра, в нее входящих ((1,2), (2,2)). Про ребро (u, v) неориентированного графа говорят, что оно инцидентно вершинам (incident on vertices) u и v. Например, на рис. 1 (б) есть два ребра, инцидентные вершине 2 (ребра (1,2) и (2,5)).

Если в графе G имеется ребро (u, v), говорят, что вершина v смежна с вершиной u (is adjacent to u). Если вершина v смежна с вершиной u в ориентированном графе, пишут u→ v. Для обоих рисунков 1(а) и 1(б) вершина 2 является смежной с вершиной 1, но лишь во втором из них вершина 1 смежна с вершиной 2 (в первом случае ребро (2,1) отсутствует в графе).

Степенью (degree) вершины в неориентированном графе называется число инцидентных ей ребер. Например, для графа рис. 1(б) степень вершины 2 равна 2. Для ориентированного графа различают исходящую степень (out-degree), определяемую как число выходящих из нее ребер, и входящую степень (in-degree), определяемую как число входящих в нее ребер. Сумма исходящей и входящей степени называется степенью вершины. Например, вершина 2 в графе рис. 1(а) имеет входящую степень 2, исходящую степень 3 и степень 5.

Путь длины k (path of length k) из вершины u в вершину v определяется как последовательность вершин 〈 v₀, v₁, v₂, ..., v_k〉, в которой v₀ = u, v_k = v и (v_i − 1, v_i) ∈ E для всех i = 1,2,…,k. Этот путь содержит (contains) вершины v₀, v₁,...,v_k и ребра (v₀, v₁), (v₁,v₂),...,(v_k − 1,v_k). Вершину v₀ называют началом пути, вершину v_k — его концом;говорят, что путь ведет из v₀ в v_k. Если для данных вершин u и u′ существует путь p из u в u′, то говорят, что вершина u′ достижима из u по пути p (u′ is reachable from u via p).

Циклом (cycle) в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл 〈 v₀, v₁, ..., v_k〉 называется простым, если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины v₁, v₂,...,v_k различны. Ребро-петля является циклом длины 1. Мы отождествляем циклы, отличающиеся сдвигом вдоль цикла: один и тот же цикл длины k может быть представлен k различными путями (в качестве начала и конца можно взять любую из k вершин). Например, на рис. 1(а) пути 〈 1, 2, 4, 1〉, 〈 2,4,1,2〉 и 〈 4,1,2,4〉 представляют один и тот же цикл. Этот цикл является простым, в то время как цикл 〈 1,2,4,5,4,1〉 таковым не является. На том же рисунке есть цикл 〈 2,2〉, образованный единственный ребром-петлей (2,2).

В неориентированном графе путь 〈 v₀, v₁, ..., v_k〉 называется (простым) циклом, если k ≥ 3, v₀ = v_k и все вершины v₁, … , v_k различны. Например, на рис. 1(б) имеется простой цикл 〈 1, 2, 5, 1〉.

Граф, в котором нет циклов, называется ациклическим (acyclic).

Неориентированный граф называется связным (connected), если для любой пары вершин существует путь из одной в другую. Максимальные по включению (нельзя добавить ни одной вершины, сохранив связность) связные подграфы называются связными компонентами (connected components) графа. Например, на рис. 1(б) имеется три связные компоненты: {1,2,5}, {3,6} и {4}. Неориентированный граф связен тогда и только тогда, когда он состоит из единственной связной компоненты.

Ориентированный граф называется сильно связным (strongly connected), если из любой его вершины достижима (по ориентированным путям) любая другая. Любой ориентированный граф можно разбить на сильно связные компоненты, которые определяются как максимальные по включению сильно связные подграфы. Ориентированный граф сильно связен тогда и только тогда, когда состоит из единственной сильно связной компоненты. Граф на рис. 1(а) имеет три таких компоненты: {1,2,4,5}, {3} и {6}. Заметим, что вершины {3,6} не входят в одну сильно связную компоненту, так как 3 достижима из 6, но не наоборот.

Упражнения

Покажите, что сумма степеней любого графа четна.

Покажите, что число нечетных вершин любого графа четно.

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

Покажите, что для любого связного неориентированного графа G = (V, E) выполняется соотношение |E| ≥ |V| − 1.

В графе G = (V, E) любая пара вершин соединена либо ребром красного цвета, либо ребром зеленого цвета. Пусть G₁ — подграф графа G, состоящий только из ребер зеленого цвета и инцидентных им вершин. Пусть, аналогично, G₂ — подграф, состоящий только из ребер красного цвета. Покажите, что либо G₁, либо G₂ является связным.

Подсказка (выделите текст, чтобы прочесть): Между любыми двумя вершинами в вышеописанном графе G существует либо полностью зеленый, либо полностью красный путь, состоящий из не более, чем двух ребер.

Задача 2. Лекция. Графы. Способы представления ≡

Условие

Рассмотрим граф G(V, E) с n = |V| вершинами v₁, ..., v_n. Его матрицей смежности (adjacency matrix) называется (n × n) — матрица a, в которой a_ij = { 1, если (v_i, v_j) ∈ E0 иначе.

Матрица смежности неориентированного графа, таким, образом, симметрична. В таком представлении мы можем за время O(1) проверить, соединены ли данные вершины ребром (посмотрев на один элемент массива). В то же время хранение матрицы требует памяти O(n²), что во многих случаях неэкономно.

Пример кода для считывания графа с n вершинами и m рёбрами в матрицу смежности.

var
    adj: array of array of Boolean;
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n, n);
    for i := 1 to m do begin
        Read(u, v);
        adj[u, v] := true;
        adj[v, u] := true;
    end;
end.

Альтернативное представление — список смежности (adjacency list). Требуемая при этом память пропорциональна размеру графа (сумме числа вершин и числа ребер). Элементами списка смежности являются массивы, по одному для каждой вершины графа. Для вершины u в таком списке хранятся вершины, в которые ведут ребра из u, т.е. вершины v, для которых (u, v) ∈ E. Для ориентированного графа каждое ребро входит только в один из этих списков (для начальной вершины), а для неориентированного — в два (для двух концов ребра). Список смежности, таким образом, требует памяти O(V + E). Проверка наличия ребра (u, v) теперь требует просмотра списка вершины u (что может быть больше O(1) шагов). Зато в этом представлении легко просмотреть всех соседей заданной вершины (что часто бывает необходимо). Список смежности для неориентированного графа симметричен (если u содержится в списке для v, то и v содержится в списке для u).

Пример кода для считывания графа с n вершинами и m рёбрами в список смежности.

var
    adj: array of array of Integer;

procedure Add(a, b: integer) begin
    SetLength(adj[a], Length(adj[a]) + 1);
    adj[a, High(adj[a])] = b;
end;

var
    n, m, u, v, i: Integer;
begin
    Read(n, m);
    SetLength(adj, n);
    for i := 1 to m do begin
        Read(u, v);
        Add(u, v);
        Add(v, u);
    end;
end.

std::vector< std::vector< int>> adj;
int n, m;
std::cin >> n >> m;
adj.resize(n);
for(int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
        

Матрица смежности или список смежности?

Что лучше? Ответ зависит от отношения между числом вершин |V| и числом ребер |E|. Заметим, что |E| может быть довольно малым — порядка |V| (если |E| сильно меньше |V|, то граф уже вырожденный — в частности, содержит изолированные вершины). Или же довольно большим — порядка |V|² (если граф содержит все возможные ребра). Графы с большим числом ребер называют плотными (dense), с малым — разреженными (sparse).

Выбирая алгоритм, полезно понимать, с какими графами ему в основном придется иметь дело. Важно это и при хранении: если хранить веб-граф, в котором больше восьми миллиардов вершин, в виде матрицы смежности, то занимать она будет миллионы терабайтов, что сравнимо с общей емкостью всех жестких дисков в мире. И дальше, скорее всего, будет только хуже (матрица может расти быстрее, чем производство дисков).

А вот хранить граф Интернета в виде списка смежности вполне разумно, поскольку хранить нужно несколько десятков миллиардов гиперссылок, каждая из которых будет занимать в списке всего несколько байтов, и такого размера диск поместится в карман. Такая разница происходит из-за того, что граф Интернета очень разрежен: страница содержит в среднем пару десятков ссылок на другие страницы — из нескольких миллиардов возможных.

Задача 3. Лекция. Графы. Поиск в глубину ≡

Условие

Прохождение лабиринтов

Поиск в глубину (depth-first search) отвечает на вопрос: какие части графа достижимы из заданной вершины? Это похоже на задачу обхода лабиринта: имея граф, как список смежности, мы в каждой вершине "видим" ее соседей — как в лабиринте, где мы видим соседние помещения (рис. 1) и можем в них перейти. Но если мы будем это делать без продуманного плана, то можем ходить кругами, а в какую-то часть так и не попасть.

Обойти лабиринт можно с помощью клубка ниток (закрепив конец нитки в исходной точке и нося клубок с собой, мы всегда сможем вернуться) и мела (чтобы отмечать, где мы уже были, и не ходить туда еще раз). Примерно так же работает алгоритм поиска в глубину. Чтобы хранить пометки, для каждой вершины будем хранить бит, показывающий, были мы в этой вершине или нет. Клубок ниток можно было бы заменить стеком (идя в новый коридор, мы добавляем его в стек, а возвращаясь обратно, забираем), но в нашем алгоритме (рис. 2) мы вместо явного стека используем рекурсию.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    { Эта функция зависит от конкретной задачи }
    { В ней или вместо нее может быть любой код, вызывающийся при посещении новой вершины }
    Previsit(v);

    { Граф хранится списками смежности (массив adj) }
    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

   { Эта функция также зависит от конкретной задачи }
    Postvisit(v);
end;

В нашем алгоритме указано также место для процедур Previsit и Postvisit (вызываемых до и после обработки вершины); мы увидим дальше, зачем это может быть полезно.

А пока нужно убедиться, что процедура Explore корректна. Ясно, что она обходит только достижимые из v вершины, поскольку на каждом шаге она переходит от вершины к ее соседу. Но обходит ли она все такие вершины? Допустим, что нашлась достижимая из v вершина u, до которой Explore почему-то не добралась. Рассмотрим тогда какой-нибудь путь из v в u. Пусть z — последняя вершина этого пути, которую посетила процедура Explore (сама вершина v, если других нет), а w — следующая сразу за z вершина на этом пути: (рис. 3).

Выходит, что вершину z процедура посетила, а вершину w — нет. Но так быть не может: ведь состоявшийся вызов Explore(z) должен был перебрать всех соседей z.

На рис. 4 показан вызов Explore для рассмотренного ранее графа и вершины A. Считаем, что соседи вершины перебираются в алфавитном порядке. Сплошными нарисованы ребра, которые ведут в ранее не встречавшиеся вершины. Например, когда процедура Explore находилась в вершине B, она прошла по ребру B − E, и, поскольку в E она до этого не бывала, был произведен вызов Explore для E. Сплошные ребра образуют дерево (связный граф без циклов) и поэтому называются древесными ребрами (tree edges). Пунктирные же ребра ведут в вершины, которые уже встречались. Такие ребра называются обратными (back edges).

Поиск в глубину

procedure Dfs;
var
    v: Integer;
begin
    for v := 1 to MaxV do
        if not used[v] then
            Explore(v);
end;

Процедура Explore обходит все вершины, достижимые из данной. Для обхода всего графа алгоритм поиска в глубину (рис. 5) последовательно вызывает Explore для всех вершин (пропуская уже посещенные).

Сразу же отметим, что процедура Explore вызывается для каждой вершины ровно один раз благодаря массиву used (пометки в лабиринте). Сколько времени уходит на обработку вершины? Она включает в себя:

• O(1)-операции: пометка вершины, а также вызовы Previsit и Postvisit (мы не учитываем время внутри этих вызовов);
• перебор соседей.

Общее время зависит от вершины, но можно оценить количество операций для всех вершин вместе. Общее количество операций на шаге 1 есть O(|V|). На шаге 2 (будем говорить о неориентированном графе) каждое ребро x,y ∈ E просматривается ровно два раза: при вызовах Explore(x) и Explore(y). Общее время работы на шаге 2, таким образом, есть O(|E|). В целом время работы поиска в глубину есть O(|V| + |E|), то есть линейно. За меньшее время мы не успеем даже прочесть все вершины и ребра.

Задача 4. Лекция. Графы. DFS в ориентированном графе. ≡

Условие

Поиск в глубину в ориентированном графе

Рассмотренный нами алгоритм поиска в глубину может быть использован и для ориентированных графов (в процедуре Explore надо перебирать выходящие из вершины ребра). На рис. 1 показан пример ориентированного графа и дерева, построенного поиском в глубину.

Вершина A называется корнем дерева (tree root), все остальные вершины этого дерева являются ее потомками E, а E является их предком (ancestor). Наконец, C является родителем (parent) D, а D — ребенком (child) C. (В отличие от людей, у вершины дерева может быть только один родитель.)

При поиске в глубину в ориентированных графах различают четыре типа ребер.

• Ребра дерева (tree edges) — ребра леса, построенного поиском в глубину.
• Прямые ребра (forward edges) ведут от вершины к ее потомку, не являющемуся при этом ее ребенком.
• Обратные ребра (back edges) ведут от вершины к ее предку.
• Перекрестные ребра (cross edges) ведут от вершины к другой вершине, не являющейся ни предком, ни потомком первой (такая вершина уже полностью обработана в момент обнаружения перекрестного ребра).

На рис. 1 можно обнаружить два прямых, два обратных и два перекрестных ребра (найдите их).

Тип ребра можно узнать по tin и tout значениям его концов. Легко видеть, что вершина u является предком v тогда и только тогда, когда v была обнаружена во время вызова Explore(u). В этом случае tin(u) < tin(v) < tout(v) < tout(u), то есть отрезок обработки v вложен в отрезок обработки u. Для обратных ребер: u — потомок v тогда и только тогда, когда v — предок u; для перекрестных ребер u − v отрезки не пересекаются (и v-отрезок предшествует u-отрезку).

Могут ли быть другие случаи расположения отрезков? Почему?

Ориентированные ациклические графы

Наличие циклов в ориентированном графе легко проверить с помощью одного вызова поиска в глубину.

Свойство. Ориентированный граф содержит цикл тогда и только тогда, когда при поиске в глубину обнаруживается обратное ребро.

Доказательство. Ясно, что если (u, v) — обратное ребро, то путь в дереве поиска в глубину от v к u и само ребро (u, v) образуют цикл.

Обратно: пусть граф содержит цикл v₀→ v₁→ ... → v_k→ v₀ и пусть v_i — вершина этого цикла, которая была обнаружена первой (то есть вершина с минимальным tin(v_i)). Все оставшиеся вершины цикла достижимы из v_i, и поэтому в дереве поиска в глубину они будут потомками v_i. Тогда ребро v_i − 1→ v_i (или же v_k→ v₀, если i = 0) ведет из вершины в ее предка, то есть является обратным ребром.

Топологическая сортировка

С помощью ориентированных ациклических графов (directed acyclic graphs или сокращенно DAGs) удобно представлять временные и иерархические отношения, а также причинно-следственные связи. Допустим, к примеру, что необходимо сделать несколько вещей, при чем есть ограничения на порядок (сначала надо проснуться и лишь потом встать с кровати; душ надо принять после того, как встал с кровати, но до того, как оделся). Как выбрать правильный порядок дел?

Ограничения представим как ориентированный граф: каждому делу соответствует вершина; ребро из u в v означает, что u должно быть выполнено до v. Если в этом графе есть цикл, то правильного порядка не существует вовсе. Если же граф ациклический, то есть надежда его топологически упорядочить (topologically sort) — так упорядочить вершины, чтобы каждое ребро вело от более ранней вершины к более поздней. Например, для графа рис. 2 один из допустимых порядков таков: B, A, D, C, E, F. (Видите ли вы еще три порядка?).

Какие же ориентированные ациклические графы можно топологически упорядочить? Оказывается, что все, и это можно сделать с помощью поиска в глубину, расположив вершины в порядке убывания их tout-значений. Ведь tout(u) < tout(v) только для обратных ребер (u, v), а мы уже знаем, что в ациклическом графе обратных ребер быть не может.

Свойство.В ориентированном ациклическом графе каждое ребро идет из вершины с бОльшим tout-значением в вершину с меньшим tout-значением.

Посмотрим на первую и последнюю вершину после топологической сортировки. Из последней вершины рёбра не выходят: как говорят, она является стоком (sink). Напротив, в первую вершину рёбра не входят: она является истоком (source). В частности, мы доказали такое утверждение:

Свойство.У каждого ациклического ориентированного графа есть хотя бы один исток и хотя бы один сток.

Заметим, что, отсортировать вершины по значению tout можно за линейное время. Для этого нужно добавлять вершины в массив в момент выхода из функции Explore

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

{ Добавляем вершину в конец с помощью глобального счетчика k }
    order[k] = v;
    k += 1;
end;

Задача 5. Лекция. Графы. DFS. Времена входа и выхода ≡

Условие

Времена входа и выхода при обходе в глубину

Вспомним процедуру обхода графа в глубину.

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;
    Previsit(v);

    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

    Postvisit(v);
end;

Поиск в глубину позволяет за линейное время определить, связен ли граф. Но это далеко не все — сейчас мы рассмотрим прием, который лежит в основе многих других применений поиска в глубину. Будем записывать время входа в каждую вершину (вызов Previsit) и время выхода (Postvisit). Для нашего примера эти числа показаны на рис. 1. Например, в момент времени 5 началась обработка вершины I, а в момент времени 21 закончилась обработка вершины D.

Чтобы сохранить эту информацию при поиске в глубину, заведем счетчик time, изначально равный 1, и напишем так:

procedure Previsit(v: integer);
begin
    tin[v] := time;
    time += 1;
end;

procedure Postvisit(v: integer);
begin
    tout[v] := time;
    time += 1;
end;

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

Свойство. Для любых двух вершин u и v либо отрезки [tin(u), tout(u)] и [tin(v), tout(v)] не пересекаются, либо один содержится в другом.

В самом деле, [tin(u), tout(u)] — это промежуток времени, в течение которого вершина u была в стеке, и если вершина v была помещена в стек, когда там уже лежала вершина u, то v будет вынута раньше u.

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

Задача 6. Лекция. Графы. Компоненты сильной связности ≡

Условие

Связность для ориентированных графов

Что означает связность для ориентированного графа? Тут надо быть аккуратным. Несвязный неориентированный граф можно разбить на связные компоненты, не соединенные друг с другом. С ориентированными графами ситуация сложнее. Граф на рис. 1 нельзя разбить на две части, не соединенные друг с другом. Но мы не будем называть этот граф связным, поскольку в нем нет пути из G в B или из F в A. Дадим такое определение:

Вершины u и v ориентированного графа называются связанными (connected), если в нем есть путь из u в v, а также путь из v в u.

Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.

Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только ребра между метавершинами (см. рис. 1), удалив дубликаты. Полученный граф называется метаграфом (meta-graph) (также графом компонент или конденсацией) исходного. Он не содержит циклов: если бы несколько компонент образовывали цикл, то вершины этих компонент были бы в исходном графе достижимы друг из друга и вошли бы в одну компоненту.

Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).

Но как построить конденсацию для данного графа? Компоненты сильной связности и метаграф могут быть построены за линейное время. Начнем с такого замечания, которое уже было доказано в предыдущих лекциях.

Свойство 1. Процедура Explore, вызванная для вершины u, заканчивает работу, когда посещены все вершины, достижимые из u.

Значит, если вызвать Explore для вершины, которая лежит в компоненте-стоке, то мы обойдем как раз все вершины этой компоненты. Например, граф рис. 1 имеет две такие компоненты, и вызов Explore для вершины K обойдет бОльшую из них.

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

Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке

Свойство 2. Вершина, которой поиск в глубину присваивает максимальное tout-значение, лежит в компоненте-истоке.

Свойство 3. Пусть C и C′ — компоненты сильной связности графа и в графе есть ориентированное ребро из C в C′. Тогда максимальное tout-значение вершин в C больше, чем максимальное tout-значение вершин в C′.

Доказательство. Дождемся момента, когда при поиске в глубину впервые появится вершина v из C или C′. Если v ∈ C, то вызов Explore(v) не завершится, пока не будут обработаны все вершины обеих компонент (по свойству 1). Поэтому tout[v] будет больше, чем у всех вершин из C′. Если же v ∈ C′, то вызов Explore(v) обойдет все вершины C′, но до C дело еще не дойдет — и максимальное tout-значение в C тоже будет больше.

Следствием этого является следующее утверждение: компоненты сильной связности можно топологически упорядочить, расположив их по убыванию максимальных tout-значений вершин в них. Это наблюдение обобщает рассмотренный нами алгоритм топологической сортировки ориентированных ациклических графов (в таких графах каждая компонента сильной связности состоит из одной вершины).

Таким образом, мы научились находить компоненту-исток и вершину в ней. Как найти все вершины только данной компоненты? Рассмотрим обращенный граф G^R, получаемый из G изменением направлений всех ребер (см. рис. 2). В G^R будут те же компоненты сильной связности, как и у G (покажите). Также, найденная вершина компоненты-истока G будет вершиной компоненты-стока графа G^R. Тогда вызов Explore из найденной вершины на графе G^R обойдет только вершины компоненты истока графа G.

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

Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.

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

1. Запустить обход в глубину графа G, который вернет вершины в порядке убывания tout. Заметим, что для этого достаточно добавлять вершину в массив при выходе Explore из этой вершины.
2. Построить обращенный граф G^R. Запустить процедуру Explore из каждой непосещённой вершины в порядке убывания tout-значений. Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.