Изменения

==Пример реализацииПсевдокод== vector<vectortex>G, H<int/tex>> g, h; //g хранит граф в виде списка смежностей, h - инвертированный vector<inttex> color, ord, component; </tex> //цвет вершины, список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина int col; //номер текущей компоненты

void '''dfs'''(int & <tex>v</tex>) //первый поиск в глубину, определяющий порядок обхода { <tex>color[v] = \leftarrow 1;</tex> '''for ''' (unsigned i = 0; всех <tex>i < g[/tex> смежных с <tex>v].size(); ++i</tex>) { '''if ''' (color[g[v][вершина <tex>i]] == 0</tex> не посещена) '''dfs'''(g<tex>G[v][i]</tex>); } ord.push_back(Добавляем вершину <tex>v); /</добавляем вершину v tex> в конец списка <tex>ord[] }</tex>

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

int '''main'''() { ... //считываем исходные данные, формируем массивы g <tex>G</tex> и h<tex>H</tex> '''for ''' (int i = 1; по всем вершинам <tex>i <= n; ++i/tex> графа <tex>G</tex>) //формируем массив ord[] { '''if ''' (color[вершина <tex>i] == 0</tex> не посещена) '''dfs'''(i); } <tex>col = \leftarrow 1;</tex> '''for ''' (int i = ord.size(); i по всем вершинам <tex> 0; --i) </tex> списка <tex>ord[]</ищем компоненты связности, вызывая вершины tex> в обратном порядке { ) //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[] '''if ''' (component[ord[если вершина <tex>i - 1]] == 0</tex> не находится ни в какой компоненте) '''dfs2'''(ord[<tex>i - 1]</tex>), <tex>col</tex>++; } }