Patterns

DFS with discovery/low-link tracking to find critical edges/vertices

When to useCritical connections, articulation points, bridges in a graph

recursive

DataCenter Critical Connection

data_center_critical_connection

Find Critical Servers

find_critical_nodes

BASE CASE

if disc[v] !== -1 (already visited), update low and skip

—

RECURSE

for unvisited neighbor v: dfs(v, u); set disc, low

for (const v of graph[u]) {

for (const v of graph[u]) {
  if (v === parent) continue;
  if (disc[v] === -1) {
    children++;
    dfs(v, u);
    low[u] = Math.min(low[u], low[v]);

update low

low[u] = min(low[u], low[v])

—

[CRITICAL]

if low[v] > disc[u], record edge (u,v) as bridge / mark articulation

—

    if (parent !== -1 && low[v] >= disc[u]) isArt[u] = true;
  } else {
    low[u] = Math.min(low[u], disc[v]);
  }

RETURN

return collected bridges/articulation points

return bridges;

return result; // nodes where isArt[i] === true