Core Traversal Mechanism

Graph connectivity problems frequently rely on a single Depth-First Search (DFS) traversal. During the traversal, two primary values are maintained for every vertex u:

• Discovery Time (disc[u]): A monotonically increasing timestamp assigned when u is first visited.
• Low-Link Value (low[u]): The smallest discovery time reachable from u (or its subtree in the DFS tree) via back-edges, without traversing the tree edge back to u's parent.

By comparing these values and utilizing an explicit recursion stack, we can identify structural weak points and maximal connected subgraphs in linear time.

Strongly Connected Components (Directed Graphs)

In a directde graph, a Strongly Connected Component (SCC) is a maximal subgraph where every vertex is mutually reachable. Tarjan’s algorithm identifies SCCs by tracking vertices currently on the recursion stack. When the DFS returns from a vertex u and finds that low[u] == disc[u], it indicates that no back-edge from the subtree of u leads to a node discovered earlier than u. At this point, all vertices above u on the stack belong to the same SCC and are popped together.

#include <vector>
#include <algorithm>
#include <iostream>

class SccSolver {
    std::vector<std::vector<int>> adj;
    std::vector<int> disc, low, stack;
    std::vector<bool> inStack;
    std::vector<int> sccId;
    int timer, sccCount;

    void dfs(int u) {
        disc[u] = low[u] = ++timer;
        stack.push_back(u);
        inStack[u] = true;

        for (int v : adj[u]) {
            if (disc[v] == 0) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = std::min(low[u], disc[v]);
            }
        }

        if (low[u] == disc[u]) {
            ++sccCount;
            while (!stack.empty() && stack.back() != u) {
                int node = stack.back();
                stack.pop_back();
                inStack[node] = false;
                sccId[node] = sccCount;
            }
            stack.pop_back();
            inStack[u] = false;
            sccId[u] = sccCount;
        }
    }

public:
    SccSolver(int n, const std::vector<std::vector<int>>& graph) 
        : adj(graph), disc(n, 0), low(n, 0), inStack(n, false), sccId(n, 0), timer(0), sccCount(0) {}

    void solve() {
        for (int i = 0; i < adj.size(); ++i)
            if (disc[i] == 0) dfs(i);
    }
};

Bridges and Edge-Biconnected Components

A bridge (or cut-edge) is an edge whose removal increases the number of connected components in an undirected graph. An edge (u, v) (where v is a child of u in the DFS tree) is a bridge if and only if low[v] > disc[u]. This condition implies that the subtree rooted at v has no back-edge connecting to u or any of its ancestors.

To distinguish tree edges from back-edges during traversal, edge identifiers are tracked. Once bridges are marked, an Edge-Biconnected Component can be found by performing a secondary traversal that skips bridged edges, labeling each resulting maximal subgraph.

#include <vector>
#include <utility>

class BridgeSolver {
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> disc, low, compLabel;
    std::vector<bool> isBridge;
    int timer, compCount;

    void findBridges(int u, int parentEdgeId) {
        disc[u] = low[u] = ++timer;
        for (auto [v, edgeId] : adj[u]) {
            if (edgeId == parentEdgeId) continue;
            
            if (disc[v] == 0) {
                findBridges(v, edgeId);
                low[u] = std::min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    isBridge[edgeId] = true;
                }
            } else {
                low[u] = std::min(low[u], disc[v]);
            }
        }
    }

    void labelComponents(int u) {
        compLabel[u] = compCount;
        for (auto [v, edgeId] : adj[u]) {
            if (compLabel[v] == 0 && !isBridge[edgeId]) {
                labelComponents(v);
            }
        }
    }

public:
    BridgeSolver(int n, const std::vector<std::vector<std::pair<int, int>>>& graph)
        : adj(graph), disc(n, 0), low(n, 0), compLabel(n, 0), isBridge(graph.size(), false), timer(0), compCount(0) {}

    void solve() {
        for (int i = 0; i < adj.size(); ++i)
            if (disc[i] == 0) findBridges(i, -1);

        for (int i = 0; i < adj.size(); ++i)
            if (compLabel[i] == 0) {
                ++compCount;
                labelComponents(i);
            }
    }
};

Articulation Points and Vertex-Biconnected Components

An articulation point (or cut vertex) is a vertex whose removal, along with its incident edges, disconnects the graph. In the DFS tree, a non-root vertex u is an articulation point if it has a child v such that low[v] >= disc[u]. The root is an articulation point only if it has two or more children in the DFS tree.

Vertex-biconnected components (also known as blocks) are maximal subgraphs that contain no articulation points. Unlike edge-biconnected components, a single articulation point can belong to multiple vertex-biconnected components. To extract them, vertiecs are pushed onto a stack during DFS. Whenever the articulation condition low[v] >= disc[u] is met, vertices are popped from the stack until v is removed. The popped set, combined with u, forms one vertex-biconnected component.

#include <vector>
#include <algorithm>

class ArticulationSolver {
    std::vector<std::vector<int>> adj;
    std::vector<int> disc, low, vertexStack;
    std::vector<bool> isArticulation;
    std::vector<std::vector<int>> biconnectedComponents;
    int timer;
    int rootVertex;

    void dfs(int u, int parent) {
        disc[u] = low[u] = ++timer;
        vertexStack.push_back(u);
        int childCount = 0;

        for (int v : adj[u]) {
            if (disc[v] == 0) {
                ++childCount;
                dfs(v, u);
                low[u] = std::min(low[u], low[v]);

                if (low[v] >= disc[u] && (u != rootVertex || childCount > 1)) {
                    isArticulation[u] = true;
                }

                if (low[v] >= disc[u]) {
                    std::vector<int> component;
                    while (!vertexStack.empty() && vertexStack.back() != v) {
                        component.push_back(vertexStack.back());
                        vertexStack.pop_back();
                    }
                    component.push_back(vertexStack.back());
                    vertexStack.pop_back();
                    component.push_back(u);
                    biconnectedComponents.push_back(component);
                }
            } else if (v != parent) {
                low[u] = std::min(low[u], disc[v]);
            }
        }
    }

public:
    ArticulationSolver(int n, const std::vector<std::vector<int>>& graph)
        : adj(graph), disc(n, 0), low(n, 0), isArticulation(n, false), timer(0) {}

    void solve() {
        for (int i = 0; i < adj.size(); ++i) {
            if (disc[i] == 0) {
                rootVertex = i;
                dfs(i, -1);
            }
        }
    }
};