Two distinct vertices in a directed graph are strongly connected if there is path in the graph from each to the other. A strongly connected component of the graph is a subset of the graph such that each pair of distinct vertices in the subset are strongly connected, and adding any more vertices to the subset would break this property.
Your challenge is to separate a graph into its strongly connected components. Specifically, you must output all of the SCCs in the graph.
I/O:
As input, you may use a list of directed edges, an adjacency list, an adjacency matrix, or any other reasonable input format. Ask if you're not sure. You may assume the graph has no totally disconnected vertices, and that there are no self edges, but you may not make any further assumptions. You may also optionally take the list of vertices as input, as well as the number of vertices.
As output, you must either give a partitioning of the vertices, such as a list of lists of vertices, where each sublist is a strongly connected component, or a labeling of vertices, where each label corresponds to a different component.
If you use a labeling, the labels must either be vertices, or a consecutive sequence of integers. This is to prevent offloafing the computation into the labels.
Examples:
These examples take lists of edges, where each edge is directed from the 1st entry to the second entry, and output partitions. You are free to use this format or another.
The input is on the first line, the output is on the second line.
[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]
[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]
[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]
[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]
Scoring and restrictions:
Standard loopholes are banned, as always. Also, built-ins which specifically deal with strongly connected components are banned.
Solutions should run in no more than an hour on the examples provided. (This is intended to prevent slow exponential solutions, and nothing else.)
This is code golf. Fewest bytes wins.
8
isn't in a component with[3,4]
because it can't can only each6
and7
(neither of which reach it). \$\endgroup\$