Identifying critical vertices and edges whose removal would disconnect a graph.
In graph theory, particularly in the context of network reliability and connectivity, identifying critical points of failure is crucial. Articulation points (also known as cut vertices) and bridges (or cut edges) represent these single points of failure. An articulation point is a vertex whose removal (along with all incident edges) increases the number of connected components of the graph. Similarly, a bridge is an edge whose removal increases the number of connected components. For example, in a network of servers, an articulation point could represent a critical server whose failure would split the network into disconnected segments. The standard algorithm to find all articulation points and bridges in a connected graph is based on a single Depth-First Search (DFS) traversal. During the DFS, we maintain two key values for each vertex `u`: a discovery time `disc[u]` (the time of first visit) and a low-link value `low[u]`. The `low[u]` value is the lowest discovery time reachable from `u` (including itself) through its DFS subtree. By comparing `disc` and `low` values of adjacent vertices, we can efficiently determine which vertices are articulation points and which edges are bridges in O(V+E) time.