# stronglyConnectedComponents<T> function Null safety

List<Set<T>> stronglyConnectedComponents<T>(
1. 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 = HashMap<T, int>();
var lowLinks = HashMap<T, int>();
var onStack = HashSet<T>();

void 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 = <T>{};
T? neighbor;
do {
neighbor = stack.removeLast();
onStack.remove(neighbor);
component.add(neighbor as T);
} 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();
}``````