изменить алгоритм Косараджу, чтобы возвращать ребра для каждой сильно связной компоненты
Ниже приведен псевдокод алгоритма Косараджу для поиска всех сильно связанных компонентов в графе.
В настоящее время он возвращает все вершины для каждого SCC.
Как его изменить, чтобы он возвращал все ребра для каждого SCC
stack STACK
void DFS(int source) {
visited[s]=true
for all neighbours X of source that are not visited:
DFS(X)
STACK.push(source)
}
CLEAR ADJACENCY_LIST
for all edges e:
first = one end point of e
second = other end point of e
ADJACENCY_LIST[second].push(first)
while STACK is not empty:
source = STACK.top()
STACK.pop()
if source is visited :
continue
else :
DFS(source)
например. в этой ссылке возвращаемый тип:
0 1 2
3
4
Я хочу, чтобы он также вернул края между ними. Итак, для первого это будет:
(2,1), (1, 0), (0, 2)
значение NULL
значение NULL
Последние два равны нулю, потому что SCC - это всего лишь отдельные узлы.