Неправильно подключен компонент Тарьяна или мой код неверен?

Question

Я пытаюсь реализовать алгоритм сильно связанного графа Тарьяна ( https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm), вот мой код, и я не понимаю, почему вершина 4 и вершина 5 также выводятся как сильно связанные компоненты?

Я использую очень простую диаграмму только для проверки 5 узлов. Мой код написан на Python 2.7.

from collections import defaultdict
class SccGraph:
    def __init__(self, vertex_size):
        self.out_neighbour = defaultdict(list)
        self.vertex = set()
        self.visited = set()
        self.index = defaultdict(int)
        self.low_index = defaultdict(int)
        self.global_index = 0
        self.visit_stack = []
        self.scc = []
    def add_edge(self, from_node, to_node):
        self.vertex.add(from_node)
        self.vertex.add(to_node)
        self.out_neighbour[from_node].append(to_node)
    def dfs_graph(self):
        for v in self.vertex:
            if v not in self.visited:
                self.dfs_node(v)
    def dfs_node(self, v):
        # for safe protection
        if v in self.visited:
            return
        self.index[v] = self.global_index
        self.low_index[v] = self.global_index
        self.global_index += 1
        self.visit_stack.append(v)
        self.visited.add(v)
        for n in self.out_neighbour[v]:
            if n not in self.visited:
                self.dfs_node(n)
                self.low_index[v] = min(self.low_index[v], self.low_index[n])
            elif n in self.visit_stack:
                self.low_index[v] = min(self.low_index[v], self.index[n])
        result = []
        if self.low_index[v] == self.index[v]:
            w = self.visit_stack.pop(-1)
            while w != v:
                result.append(w)
                w = self.visit_stack.pop(-1)
            result.append(v)
            self.scc.append(result)

if __name__ == "__main__":
    g = SccGraph(5)
    # setup a graph 1->2->3 and 3 -> 1 which forms a scc
    # setup another two edges 3->4 and 4->5
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,1)
    g.add_edge(3,4)
    g.add_edge(4,5)
    g.dfs_graph()
    print g.scc

Answer 1

Каждая вершина сильно связана. Если он не принадлежит какому-либо большему сильно связанному подграфу, то это уже сильный компонент. Так что и ваша реализация, и алгоритм Тарьяна в порядке. (Я не проверял, есть ли у вас другие ошибки).