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