Изменения
→Пример реализации
Теперь докажем, что если ''s'' и ''t'' находятся в одном дереве поиска, то они являются сильно связанными. Пусть ''r'' - корень этого дерева. Тогда ''s'' достижима из ''r'', из чего следует, что в обратном графе ''r'' достижима из ''s''. Но ''r'' имеет большее время окончания обработки f[r] > f[s], из чего следует что в обратном графе существует путь из ''r'' в ''s''. Тогда в исходном графе существуют пути как из ''s'' в ''r'', так и из ''r'' в ''s'', т.е. ''r'' и ''s'' сильно связаны. Те же рассуждения доказывают, что ''t'' и ''r'' сильно связаны, из чего следует что ''t'' и ''s'' также сильно связаны.
==Пример реализации==
vector<vector<int>> g, g1; //g хранит граф в виде списка смежностей, g1 - обратный vector<int> color, ord, component; //цвет вершины, список вершин в порядке окончания обработки, номер компоненты, к который относиться вершина int col; //номер текущей компоненты void dfs(int & v) //первый поиск в глубину, определяющий порядок обхода
{
color[v] = 1;
dfs(g[v][i]);
}
ord.push_back(v);
}
void dfs2(int & v) //второй поиск в глубину, выявляет компоненты сильной связности в графе
{
for (unsigned i = 0; i < g1[v].size(); i ++ )
{
if (colorcomponent[g1[v][i]] == 0)
dfs2(g1[v][i]);
}
{
...
for (int i = 1; i <= n; ++i) //формируем массив ord[]
{
if (color[i] == 0)
}
col = 1;
for (int i = ord.size(); i > 0; --i) //ищем компоненты связности, вызывая вершины в обратном порядке { //от сохранённого в ord[], что соответствует уменьшению времени конца обработки f[] if (colorcomponent[ord[i - 1]] == 0)
dfs2(ord[i - 1]), col++;
}
}
