Изменения

Данная задачи решается [[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]][[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связности]] в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину ]] в 3 этапа:

#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - — время окончания обработки вершины <tex>u</tex>

Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - — на <tex>H</tex>.<br clear = "all"> 

Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они оказываются принадлежат одному дереву обхода в одной [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связанности]]глубину.

Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то во время выполнения третьего шага на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины окажутся лежат в одном поддереве по свойству обхода в глубина. Следовательно они будут находится в одной компоненте сильной связности.

1) Рассмотрим корень # Вершины <tex>s</tex> и <tex>t</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева второго обхода . # Вершина <tex>r</tex> была рассмотрена вторым обходом в глубинураньше, чем <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе в котором оказались вершины глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Это значит, что Из этого мы получаем 2 случая:##Обе эти вершины были достижимы из <tex>r</tex> в инвертированном графе . А это означает взаимную достижимость вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>Gs</tex> существует путь и <tex>t</tex>.##Хотя бы одна не достижима из <tex>r</tex> в инвертированном графе, например <tex>st</tex> . Значит и <tex>r</tex> была не достижима из <tex>t</tex> в инвертированном графе, так как время выхода <tex>r</tex> - больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что <tex>t</tex>была достижима из <tex>r</tex> по пункту 1).

Значит, из случая 2) Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше.1 и не существования случая 2.2 получаем, чем что вершины <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе взаимно достижимы в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>обоих графах. Из этого мы получаем 2 случая:}}

а) Обе эти вершины были достижимы из ==Время работы алгоритма==#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>rO(V + E)</tex> действий. Для матричного представления графа не нужно выполнять никакие действия для его инвертирования.#Количество ребер в инвертированном равно количеству ребер в изначальном графе. А это означает взаимную достижимость вершин , поэтому поиск в глубину будет работать за <tex>sO(V + E)</tex> и #Поиск в глубину в исходном графе выполняется за <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>tO(V + E)</tex>. А складывая пути мы В итоге получаем взаимную достижимость вершин , что время работы алгоритма <tex>s</tex> и <tex>tO(V + E)</tex>.

б) Между ==Псевдокод==Пусть <tex>rG</tex> и этими вершинами вообще нет пути ни в одну сторону— исходный граф, ни в другую при первом обходе в инверитированном графе. Но последнего быть не может, так как эти вершины были достижимы из <tex>rH</tex> в графе —инвертированный граф. В массиве <tex>Gord</tex>, а значит, вершина <tex>r</tex> достижима из них будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>HG</tex>.  Значит, из случая а) и не существования случая б) В результате получаем, что вершины массив <tex>scomponent</tex> и <tex>t</tex> взаимно достижимы в обоих графах.}} ==Пример реализации== vector<vector<int>> g, h; //g хранит граф в виде списка смежностей, h - инвертированный vector<int> color, ord, component; //цвет вершины, список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина int col; //каждой вершине сопоставляет номер текущей её компоненты.

void dfs'''function''' dfs1(int & v) : //первый поиск в глубину, определяющий порядок обхода { color[v] = 1; '''for ''' (unsigned i = 0; i < g[v].size(, u); ++i) {'''in''' E '''if (color[g[v]''' '''not''' visited[i]u] == 0) dfsdfs1(gG[v][iu]); } ord.push_back(v); //добавляем Добавляем вершину v в конец списка ord[] }

void '''function''' dfs2(int & v) //второй поиск в глубину, выявляет компоненты сильной связности в графе {: component[v] = col; //помечаем вершину v как принадлежащую компоненте с номером col '''for ''' (unsigned i = 0; i < h[v].size(, u); ++i) {'''in''' E '''if ''' (component[h[v][i]] == 0вершина u еще не находится ни в какой компоненте) dfs2(hH[v][iu]); } }

int '''function''' main() {: ... //считываем исходные данные, формируем массивы g G и hH '''for (int i = 1; i <= n; ++i) ''' u '''in''' V //формируем массив ord[] { '''if (color''' '''not''' visited[iu] == 0) dfsdfs1(iu); } col = 1; '''for ''' (int i = по всем вершинам u списка ord.size(); i > 0; --i) //ищем компоненты связности, вызывая вершины [] в обратном порядке { //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[]) '''if ''' (component[ord[i - 1]] == 0вершина u не находится ни в какой компоненте) dfs2(ord[i - 1]u), col++; } } По окончании выполнения алгоритма в <tex>component[i]</tex> имеем номер компоненты, к которой принадлежит вершина <tex>i</tex>.

==ЛитератураИсточники информации==