为文件中的整数实现强连接组件

Question

5 5
1 2
2 4
2 3
3 4
4 5

DFS(G)
1 for each vertex u in G.V
2     u.color = WHITE
3     u.π = NIL
4 time = 0
5 for each vertex u in G.V
6     if u.color == WHITE
7         DFS-VISIT(G, u)

DFS-VISIT(G, u)
1 time = time + 1 // white vertex u has just been discovered
2 u.d = time
3 u.color = GRAY
4 for each v in G.adj[u]
5     if v.color == WHITE
6         v.π = u
7         DFS-VISIT(G, u)
8 u.color = BLACK // blacken u; it is finished
9 time = time + 1
10 u.f = time

在上面的算法中，我应该如何遍历反向图来找到SCC。

Answer 1

这里，用Python实现。

请注意我同时构造G和G'。我的DFS也被修改。访问的数组存储每个节点所在的组件。此外，DFS还接收sequence参数，即测试节点的顺序。在第一个DFS中，我们传递一个xrange(n)，但在第二次中，我们传递第一次执行的反向（顺序）。

该程序将输出如下内容：

3
[1, 1, 1, 2, 3]

def DFSvisit(G, v, visited, order, component):
    visited[v] = component
    for w in G[v]:
        if not visited[w]:
            DFSvisit(G, w, visited, order, component)
    order.append(v);

def DFS(G, sequence, visited, order):
    components = 0
    for v in sequence:
        if not visited[v]:
            components += 1
            DFSvisit(G, v, visited, order, components)

n, m = (int(i) for i in raw_input().strip().split())

G = [[] for i in xrange(n)]
Gt = [[] for i in xrange(n)]
for i in xrange(m):
    a, b = (int(i) for i in raw_input().strip().split())
    G[a-1].append(b-1)
    Gt[b-1].append(a-1)

order = []
components = [0]*n

DFS(G, xrange(n), [0]*n, order)
DFS(Gt, reversed(order), components, [])

print max(components)
print components