kosarajuSCC<T> function

List<Set<T>> kosarajuSCC<T>(Map<T, List<T>> graph)

Implementation

List<Set<T>> kosarajuSCC<T>(Map<T, List<T>> graph) {
  final Set<T> nodes = {...graph.keys};
  for (final neighbors in graph.values) {
    nodes.addAll(neighbors);
  }

  final Set<T> visited = <T>{};
  final List<T> order = <T>[];

  void dfs1(T u) {
    visited.add(u);
    for (final v in graph[u] ?? const []) {
      if (!visited.contains(v)) dfs1(v);
    }
    order.add(u);
  }

  for (final n in nodes) {
    if (!visited.contains(n)) dfs1(n);
  }

  final rg = _reverseGraph(graph);
  visited.clear();
  final List<Set<T>> components = [];

  void dfs2(T u, Set<T> comp) {
    visited.add(u);
    comp.add(u);
    for (final v in rg[u] ?? const []) {
      if (!visited.contains(v)) dfs2(v, comp);
    }
  }

  for (final u in order.reversed) {
    if (!visited.contains(u)) {
      final Set<T> comp = <T>{};
      dfs2(u, comp);
      components.add(comp);
    }
  }

  return components;
}