Kata

Strongly connected components

Let $VV$ be the set of vertices of the graph. A strongly connected component $SS$ of a directed graph is a maximal subset of its vertices $S\subseteq VS\; \subseteq \; V$, so that there is an oriented path from any vertex $v\in Sv\; \in \; S$ to any other vertex $u\in Su\; \backslash in\; S$.

Example

In this graph, strongly connected components are

[{a, b, e}, {f, g}, {c, d ,h}]

Task

Write a function strongly_connected_components which accepts a graph represented as an adjacency list, and returns a list containing set of connected components.

Examples:

# Graph from the image
# The vertexes are numbered as follows: 
# (0, 1, 2, 3, 4, 5, 6, 7) = (a, b, e, f, c, g, d, h).
# The list in the i-th position of the adjacency list 
# contains vertices that have an incoming edge from vertex i.
# For example, from vertex 1 <=> (b), you can get to vertices 
# [2, 3, 4] <=> (e, f, c).
>>> graph = [[1], [2, 3, 4], [0, 3], [5], 
             [5, 6], [3], [4, 7], [5, 6]]
>>> strongly_connected_components(graph)
[{3, 5}, {4, 6, 7}, {0, 1, 2}]

# One more sample
>>> graph = [[1], [2], [3, 4], [0], [5], [6], [4, 7], []]
>>> strongly_connected_components(graph)
[{7}, {4, 5, 6}, {0, 1, 2, 3}]

Note: in python scipy is disabled.