изменить алгоритм Косараджу, чтобы возвращать ребра для каждой сильно связной компоненты

Ниже приведен псевдокод алгоритма Косараджу для поиска всех сильно связанных компонентов в графе.

В настоящее время он возвращает все вершины для каждого 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 - это всего лишь отдельные узлы.

0 ответов

Другие вопросы по тегам