DFS with low-link

int[] disc, low;
int time = 0;
Set bridges = new HashSet<>();
Set articulations = new HashSet<>();
void dfs(int u, int parent) {
  disc[u] = low[u] = time++;
  int children = 0;
  for (int v : graph[u]) {
    if (v == parent) continue;
    if (disc[v] == -1) {
      children++;
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u]) bridges.add(new int[]{u, v});
      if (parent != -1 && low[v] >= disc[u]) articulations.add(u);
    } else {
      low[u] = min(low[u], disc[v]);
    }
  }
  if (parent == -1 && children > 1) articulations.add(u);
}
Advertisement

Bridge condition

Edge (u,v) is a bridge iff low[v] > disc[u]. No back edge from v's subtree reaches u or higher.

Advertisement

Articulation condition

Vertex u is articulation iff root with 2+ children OR non-root with low[v] ≥ disc[u] for some child v.

Complexity

O(V + E).