hasCycleDirected<T> function

bool hasCycleDirected<T>(
  1. Map<T, List<T>> graph
)

Implementation

bool hasCycleDirected<T>(Map<T, List<T>> graph) {
  final Set<T> visiting = <T>{};
  final Set<T> visited = <T>{};

  bool dfs(T node) {
    if (visiting.contains(node)) return true;
    if (visited.contains(node)) return false;
    visiting.add(node);
    for (final T neighbor in graph[node] ?? const []) {
      if (dfs(neighbor)) return true;
    }
    visiting.remove(node);
    visited.add(node);
    return false;
  }

  final Set<T> nodes = {...graph.keys};
  for (final neighbors in graph.values) {
    nodes.addAll(neighbors);
  }
  for (final T node in nodes) {
    if (!visited.contains(node)) {
      if (dfs(node)) return true;
    }
  }
  return false;
}