# stronglyConnectedComponents<T> function

List<Set<T>> stronglyConnectedComponents <T>(Map<T, Iterable<T>> graph)

Returns the strongly connected components of `graph`, in topological order.

Interprets `graph` as a directed graph with a vertex for each key and edges from each key to the values that the key maps to.

Assumes that every vertex in the graph has a key to represent it, even if that vertex has no outgoing edges. This isn't checked, but if it's not satisfied, the function may crash or provide unexpected output. For example, `{"a": ["b"]}` is not valid, but `{"a": ["b"], "b": []}` is.

## Implementation

``````List<Set<T>> stronglyConnectedComponents<T>(Map<T, Iterable<T>> graph) {
// This uses [Tarjan's algorithm][].
//
// [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
var index = 0;
var stack = <T>[];
var result = <Set<T>>[];

// The order of these doesn't matter, so we use un-linked implementations to
// avoid unnecessary overhead.
var indices = new HashMap<T, int>();
var lowLinks = new HashMap<T, int>();
var onStack = new HashSet<T>();

strongConnect(T vertex) {
indices[vertex] = index;
index++;

for (var successor in graph[vertex]) {
if (!indices.containsKey(successor)) {
strongConnect(successor);
} else if (onStack.contains(successor)) {
}
}

if (lowLinks[vertex] == indices[vertex]) {
var component = new Set<T>();
T neighbor;
do {
neighbor = stack.removeLast();
onStack.remove(neighbor);