"""
Tarjan's Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm
for finding the strongly connected components of a graph.
"""

def strongly_connected_components(graph):
    index_counter = [0]
    stack = []
    lowlinks = {}
    index = {}
    result = []

    def strongconnect(node):
        # set the depth index for this node to the smallest unused index
        index[node] = index_counter[0]
        lowlinks[node] = index_counter[0]
        index_counter[0] += 1
        stack.append(node)
        # Consider successors of `node`
        try:
            successors = graph[node]
        except:
            successors = []
        for successor in successors:
            if successor not in lowlinks:
                # Successor has not yet been visited; recurse on it
                strongconnect(successor)
                lowlinks[node] = min(lowlinks[node], lowlinks[successor])
            elif successor in stack:
                # the successor is in the stack and hence in the current SCC
                lowlinks[node] = min(lowlinks[node], index[successor])
        # If node is a root node, pop the stack and generate an SCC
        if lowlinks[node] == index[node]:
            connected_component = []
            while True:
                successor = stack.pop()
                connected_component.append(successor)
                if successor == node: break
            component = tuple(connected_component)
            # storing the result
            result.append(component)
    for node in graph:
        if node not in lowlinks:
            strongconnect(node)
    return result

if __name__ == "__main__":
    graph = {'a': ['b', 'd', 'f'],
             'b': ['c'],
             'c': ['a', 'e'],
             'd': ['b', 'e'],
             'e': ['b', 'f']}

    print strongly_connected_components(graph)
