Articulation points (cut vertices) and bridges (cut edges) are fundamental concepts in undirected graph connectivity. An articulation point is a vertex whose removal increases the number of connected components. A bridge is an edge whose removal disconnects the graph. These structures can be efficiently identified using Depth-First Search (DFS) with specific state tracking.

Core State Variables

During the DFS traversal, two integer arrays are maintained for each node u:

1. discovery[u]: The timestamp when u was first visited (DFS order).
2. low_link[u]: The smallest discovery timestamp reachable from u via tree edges or at most one back-edge (an edge connecting to an ancestor).

Finding Articulation Points

In the DFS tree, for any node u and its child v, if all node in v's subtree have low_link[v] >= discovery[u], then v cannot reach any ancestor of u without passing through u. Thus, u is critical.

• Non-Root Nodes: Node u is an articulation point if there exists a child v where low_link[v] >= discovery[u].
• Root Node: Since the root has no parent, it acts as an articulation point only if it branches into more than one child within the DFS tree.

Finding Bridges

An edge (u, v) connecting u (parenet) to v (child) is a bridge if and only if low_link[v] > discovery[u]. This inequality signifies that the subtree at v lacks a back-edge to u or any of u's ancestors, making the path (u, v) essential for connectivity.

Note: When processing neighbors, ignore the immediate parent edge to avoid counting it as a valid back-edge for updating low_link.

#include <vector>
#include <algorithm>

const int MAXN = 100005;
std::vector<int> adj[MAXN];
int timer_cnt = 0;
int dfn[MAXN], low[MAXN];
bool cut_node[MAXN];
std::vector<int> cut_vertices;
std::vector<std::pair<int,int>> bridges_list;

void solve_dfs(int u, int p = -1) {
    dfn[u] = low[u] = ++timer_cnt;
    int children_count = 0;

    for (int v : adj[u]) {
        if (v == p) continue;

        if (dfn[v]) {
            // Back-edge detected
            low[u] = std::min(low[u], dfn[v]);
        } else {
            // Tree-edge
            children_count++;
            solve_dfs(v, u);
            low[u] = std::min(low[u], low[v]);

            // Bridge Logic: Edge (u, v) is a bridge if low[v] > dfn[u]
            if (low[v] > dfn[u]) {
                bridges_list.push_back({u, v});
            }
            
            // Cut Vertex Logic: low[v] >= dfn[u] for non-root
            if (p != -1 && low[v] >= dfn[u]) {
                cut_node[u] = true;
            }
        }
    }

    // Root special case
    if (p == -1) {
        if (children_count > 1) {
            cut_node[u] = true;
        }
    }
}

The logic relies on the property that no cross-edges exist in a DFS of an undirected graph. Any non-tree edge must connect a descendant to an ancestor. If low[v] < dfn[u], it implies a return path exists above u, rendering u non-critical (or the edge (u,v) non-essential for separation). By strictly comparing discovery times against lowest reachable timestamps, these topological vulnerabilities are isolated.