reachabilitySets function

List<Set<int>> reachabilitySets(
  1. Adjacency graph
)

For each node, the set of nodes reachable from it via one or more edges.

result[i] excludes i unless i can return to itself through a cycle, so a self-loop or any back-path puts i in its own set. The traversal explores each node's descendants with BFS, so even cyclic graphs terminate.

Example:

final Adjacency g = buildGraph([(0, 1), (1, 2)], 3);
reachabilitySets(g); // [{1, 2}, {2}, {}]

Audited: 2026-06-12 11:26 EDT

Implementation

List<Set<int>> reachabilitySets(Adjacency graph) => <Set<int>>[
  for (int i = 0; i < graph.length; i++) _reachableFrom(graph, i),
];