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).