*<Null safety>*
List<Set<T>> stronglyConnectedComponents <T>(Map<T, Iterable<T>> graph)
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(); }