Python Tarjan算法

NO_ROAD = -1
node_num = 6
dfn = 0
scc_count = 0

graph = [[ NO_ROAD for col in range( node_num ) ]          for raw in range( node_num )]

IsInStack = [False] * node_num
stack = []

class Node:
    def __init__( self ):
        self.low = -1
        self.dfn = -1

node_arr = [ Node() for index in range( node_num ) ]

def init():
    graph[0][1] = graph[0][2] = graph[1][3] = 1
    graph[2][3] = graph[2][4] = graph[3][0] = 1
    graph[3][5] = graph[4][5] = 1
    for index in range( node_num ):
        node_arr[index].index = index
 
def tarjan( index ):
    global dfn, node_num, scc_count, IsInStack, stack
    node_arr[index].dfn = dfn
    node_arr[index].low = dfn
    dfn += 1
    IsInStack[index] = True
    stack.append( index )
    for i in range( node_num ):
        if graph[index][i] != NO_ROAD:
            if node_arr[i].dfn == -1:
                tarjan( i )
                node_arr[index].low = min( node_arr[index].low,                                           node_arr[i].low )
            elif IsInStack[i]:
                node_arr[index].low = min( node_arr[index].low,                                           node_arr[i].dfn )

    if node_arr[index].low == node_arr[index].dfn:
        scc_count += 1
        print ‘SCC %d:‘%scc_count
        out_item = None
        while out_item != index:
            out_item = stack.pop()
            IsInStack[out_item] = False
            print out_item
def solve():
    for index in range( node_num ):
        if node_arr[index].dfn == -1:
            tarjan( index )

if __name__ == ‘__main__‘:
    init()
    solve()