Изменения
→Псевдокод
Пусть <tex>G</tex> — исходный граф, <tex>H</tex> —инвертированный граф. В массиве <tex>ord</tex> будем хранить номера вершин в порядке окончания обработки поиском в глубину в графе <tex>G</tex>. В результате получаем массив <tex>component</tex>, который каждой вершине сопоставляет номер её компоненты.
'''dfs1function'''dfs1(<tex>v</tex>) <tex>color[v] \leftarrow = 1</tex> '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>) '''if''' (вершина <tex>i</tex> не посещена) '''dfs1'''(<tex>G[v][i]</tex>) Добавляем вершину <tex>v</tex> в конец списка <tex>ord</tex>
'''dfs2function'''dfs2(<tex>v</tex>) <tex>component[v] \leftarrow = col</tex> '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>) '''if''' (если вершина <tex>i</tex> еще не находится ни в какой компоненте) '''dfs2'''(<tex>H[v][i]</tex>)
'''mainfunction'''main() считываем исходные данные, формируем массивы <tex>G</tex> и <tex>H</tex> '''for''' (по всем вершинам <tex>i</tex> графа <tex>G</tex>) '''if''' (вершина <tex>i</tex> не посещена) '''dfs1'''(i) <tex>col \leftarrow = 1</tex> '''for''' (по всем вершинам <tex>i</tex> списка <tex>ord[]</tex> в обратном порядке) '''if''' (если вершина <tex>i</tex> не находится ни в какой компоненте) '''dfs2'''(<tex>i</tex>) <tex>col</tex>++
==Литература==
