kosaraju.py

import time
from collections import deque
import sys
sys.setrecursionlimit(10000)


class Node(object):
    def __init__(self, name):
        self.name = name
        self.explored = False
        self.ft = None
        self.adjacent = []
        self.adjacent_inv = []
        self.leader = None


def DFSloop(graph, mode='forward'):
    global t, S
    for node in reversed(graph):
        if not node.explored:
            if mode == 'backward':
                S = node
            DFS_norecurse(node, mode)


def DFS(node, mode='forward'):
    global t, S
    node.explored = True
    if mode == 'backward':
        node.leader = S
        for n in node.adjacent_inv:
            if not n.explored:
                DFS(n, mode)
    elif mode == 'forward':
        for n in node.adjacent:
            if not n.explored:
                DFS(n, mode)
        t += 1
        node.ft = t


def DFS_norecurse(root_node, mode='forward'):
    global t, S
    queue = deque([root_node])
    if mode == 'forward':
        while queue:
            node = queue.popleft()
            if not node.explored:
                node.explored = True
                queue.appendleft(node)
                queue.extendleft(reversed([n for n in node.adjacent if not n.explored]))
            else:
                if not node.ft:
                    t += 1
                    node.ft = t
    elif mode == 'backward':
        while queue:
            node = queue.popleft()
            if not node.explored:
                node.leader = S
                node.explored = True
                queue.extendleft(reversed(node.adjacent_inv))


if __name__ == '__main__':
    now = time.time()
    t = 0
    S = None
    with open('input100k.txt') as f:
        data = f.readlines()
    data = [[int(num) for num in row.rstrip().split(' ')] for row in data]
    graph = [Node(i) for i in xrange(1, max(max(data)) + 1)]
    for edge in data:
        graph[edge[0] - 1].adjacent.append(graph[edge[1] - 1])
        graph[edge[1] - 1].adjacent_inv.append(graph[edge[0] - 1])
    DFSloop(graph)
    graph = sorted(graph, key=lambda node: node.ft)
    for node in graph: node.explored = False
    DFSloop(graph, mode='backward')
    leaders = sorted([node.leader.name for node in graph])
    scc_sizes = []
    i = leaders[0]
    count = 1
    for leader in leaders[1:]:
        if i == leader:
            count += 1
        else:
            i = leader
            scc_sizes.append(count)
            count = 1
    scc_sizes.append(count)
    scc_sizes = sorted(scc_sizes)
    if scc_sizes < 5:
        print scc_sizes
    else:
        print scc_sizes[-5:]  # [211, 313, 459, 968, 434821]
    print time.time() - now  # 69.4064071178

Ran on a MacBook Air early 2015