articulationPoints<T> function

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

Implementation

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

  final Map<T, int> disc = <T, int>{};
  final Map<T, int> low = <T, int>{};
  final Map<T, T?> parent = <T, T?>{};
  final Set<T> ap = <T>{};
  int time = 0;

  void dfs(T u) {
    disc[u] = low[u] = ++time;
    int childCount = 0;
    for (final v in graph[u] ?? const []) {
      if (!disc.containsKey(v)) {
        parent[v] = u;
        childCount++;
        dfs(v);
        low[u] = (low[u]!.compareTo(low[v]!) < 0) ? low[u]! : low[v]!;
        if (parent[u] != null && low[v]! >= disc[u]!) {
          ap.add(u);
        }
      } else if (v != parent[u]) {
        low[u] = (low[u]!.compareTo(disc[v]!) < 0) ? low[u]! : disc[v]!;
      }
    }
    if (parent[u] == null && childCount > 1) {
      ap.add(u);
    }
  }

  for (final n in nodes) {
    if (!disc.containsKey(n)) {
      parent[n] = null;
      dfs(n);
    }
  }
  return ap;
}