eolymp

Сильно связные компоненты

   Определение. Ориентированный граф называется сильно связным, если из любой вершины достижима любая другая (по ориентированным дугам).

   Произвольный ориентированный граф можно разбить на сильно связные компоненты, которые определяются как классы эквивалентности "u достижимо из v иv достижимо из u".

   Теорема. Граф является сильно связным (то есть состоит из одной сильно связной компоненты) тогда и только тогда, когда для любой вершины v выполняются следующие два условия:

  • из вершины v достижимы все другие вершины графа;
  • из любой вершины графа достижима вершина v;

   Определение. Сильно связной компонентой ориентированного графа G(V, E)называется такое максимальное множество вершин C TM_podmn_and_ravno V, что для каждой пары вершин u и v из C вершины u и v достижимы друг из друга.

   Определение. Транспонированием графа G(V, E) называется граф GT(V, ET),

в котором E= {(uv) : (vuTM_in E}.

   Графы G и GT имеют одни и те же сильно связные компоненты, так как u идостижимы друг из друга в G тогда и только тогда, когда они достижимы друг из друга в GT.

   Следующий алгоритм Косарайю за линейное время O(V + E) находит сильно связные компоненты ориентированного графа G(V, E).

   Strongly Connected Components(G)

   1. Вызываем поиск в глубину DFS(G), вычисляем метки завершения f[v] для каждой вершины v TM_in V.

   2. Строим транспонированный граф GT.

   3. Вызываем поиск в глубину DFS(GT), но в главном цикле процедурыDFS рассматриваем вершины в порядке убывания значений f[v].

   4. Деревья леса поиска в глубину, полученного в пункте 3, представляют собой сильно связные компоненты.

   На основе этого алгоритма определяется граф компонент GSCC(VSCC, ESCC)следующим образом. Пусть граф G имеет сильно связанные компоненты C1C2, …, Ck. Множество вершин VSCC = {v1v2, …, vk} состоит из вершин vi для каждого сильно связного компонента Ci графа G.

   Пример. Рассмотрим выполнение алгоритма вычисления сильно связных компонент на примере.

   1. Вызываем DFS(G), возле каждой вершины v расставляем метки d[v] / f[v]:

SCC-01

   2. Вычисляем GT:

SCC-02

   3. Вызываем DFS(GT), рассматривая вершины в порядке убывания значений f[v]. Получаем граф компонентов:

SCC-03

   4. Сильно связными компонентами в графе будут: {abe}{cd}{fg} и {h}.

   Лемма. Пусть C1 и C2 – различные сильно связные компоненты в ориентированном графе G(V, E). Пусть u1v1 TM_in C1u2v2 TM_in C2, а также в G имеется путь u1 arrow-right u2. Тогда в G не может быть пути v2 arrow-right v1.

   Доказательство. Если предположить обратное, то вершины u1 и u2 будут достижимы одна из другой (u2 arrow-right v2 arrow-right v1 arrow-right u1). То есть эти вершины должны входить в одну сильно связную компоненту.

   Пусть U TM_podmn_and_ravno V. Определим d(U) = SCC-05f(U) = SCC-06. То есть d(U)и  f(U) представляют собой самое раннее время открытия и самое позднее время завершения для всех вершин из U.

   Лемма. Пусть C1 и C2 – различные сильно связные компоненты в ориентированном графе G(V, E). Пусть имеется ребро (uv) TM_in E, где u TM_in C1v TM_in C2. Тогда f(C1) >f(C2).

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

   Вход. Первая строка содержит количество вершин n в графе. Каждая следующая строка описывает ориентированное ребро графа и содержит номера вершин, которые оно соединяет. Вершины графа нумеруются числами от 1 до n.

   Выход. Для каждой компоненты сильной связности вывести ее порядковый номер, а также список вершин, в нее входящих, в порядке возрастания. Компоненты следует выводить в произвольном порядке.   

Пример входа

Пример выхода

8

Component 1: 1 5 2

1 2

Component 2: 3 4

2 3

Component 3: 7 6

2 5

Component 4: 8

2 6

 

3 4

 

3 7

 

4 3

 

4 8

 

5 1

 

5 6

 

6 7

 

7 6

 

7 8

 

   Граф, изображенный в примере, с расставленными метками обхода в глубину имеет вид:

SCC-04

   Информацию о ребрах графа будем хранить в списке смежности gg[i] является списком, содержащим номера вершин, с которыми связана вершина i. Соответственно информация о транспонированном графе будет содержаться в списке смежности gr.

vector<vector<int> > g, gr;

   Объявленные списки смежности заполняем следующим образом:

scanf("%d",&n);

g.assign(n+1,0);gr.assign(n+1,0);

while(scanf("%d %d",&a,&b) == 2)

  g[a].push_back(b), gr[b].push_back(a);

   Массив used будем использовать для хранения информации о пройденных вершинах при поиске в глубину. Массив list будет содержать список вершин графа по окончании первого обхода в глубину в порядке убывания меток f[v]. В массив component будут заноситься все вершины очередной найденной сильно связанной компоненты.

vector<int> used, list, component;

   Вызов первого поиска в глубину:

used.assign(n+1,0);

for(i = 1; i <= n; i++)

  if (!used[i]) dfs1(i);

   При первом поиске в глубину строится массив list. По его завершению массив listравен {8, 4, 6, 7, 3, 5, 2, 1}.

void dfs1(int v)

{

  used[v] = 1;

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

  {

    int to = g[v][i];

    if (!used[to]) dfs1(to);

  }

  list.push_back(v);

}

   В порядке убывания значений f[v] перебираем вершины графа (для этого двигаемся по массиву list с конца в начало). Если мы еще не были в очередной вершине v, то вызываем из нее второй поиск в глубину. В переменной с подсчитываем количество найденных компонент сильной связности. Множество вершин, входящих в очередную компоненту, содержится в массиве component.

used.assign(n+1,0); c = 0;

for(i = 1; i <= n; i++)

{

  v = list[n-i];

  if (!used[v])

  {

    component.clear();

    dfs2(v); c++;

    // вывод компоненты

    printf("Component %d: ",c);

    for(j = 0; j < component.size(); j++)

      printf("%d ",component[j]);

    printf("\n");

  }

}

   Второй поиск в глубину совершается по транспонированному графу. В нем заполняется массив component для каждой компоненты сильной связности.

void dfs2(int v)

{

  used[v] = 1; component.push_back(v);

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

  {

    int to = gr[v][i];

    if (!used[to]) dfs2(to);

  }

}

 

Литература и источники

  1. ...