# 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;
lowLinks[vertex] = index;
index++;

stack.add(vertex);
onStack.add(vertex);

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

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

for (var vertex in graph.keys) {
if (!indices.containsKey(vertex)) strongConnect(vertex);
}

// Tarjan's algorithm produces a reverse-topological sort, so we reverse it to
// get a normal topological sort.
return result.reversed.toList();
}