Strongly Connected Components

Core Definitions

In directed graphs, two vertices u and v are strongly connected if there exists a directed path from u to v and from v to u. A strongly connected component (SCC) is a maximal subgraph where every pair of vertices is strongly connected. These components enable graph condensation into a directed acyclic graph (DAG), simplifying complex network analysis.

Algorithm Mechanics

The algorithm performs a single depth-first search while tracking two timestamps per vertex:

• discovery[vertex]: Records when the vertex is first visited
• lowlink[vertex]: Stores the smallest discovery time reachable from the vertex through its descendants and back edges

A stack maintains the current DFS path. When a vertex's lowlink equals its discovery time, it serves as the root of an SCC, and all vertices above it in the stack belong to that component.

Implementation

void identify_scc(int vertex) {
    discovery[vertex] = lowlink[vertex] = ++time_counter;
    vertex_stack.push(vertex);
    on_stack[vertex] = true;
    
    for (int neighbor : graph[vertex]) {
        if (!discovery[neighbor]) {
            identify_scc(neighbor);
            lowlink[vertex] = min(lowlink[vertex], lowlink[neighbor]);
        } else if (on_stack[neighbor]) {
            lowlink[vertex] = min(lowlink[vertex], discovery[neighbor]);
        }
    }
    
    if (lowlink[vertex] == discovery[vertex]) {
        ++component_count;
        int size = 0;
        
        while (true) {
            int member = vertex_stack.top();
            vertex_stack.pop();
            on_stack[member] = false;
            component_id[member] = component_count;
            ++size;
            if (member == vertex) break;
        }
        
        if (size > 1) ++non_trivial_sccs;
    }
}

Articulation Points

Concept

An articulation point (or cut vertex) in a undirected graph is a vertex whose removal increases the number of connected components. These vertices represent critical failure points in networks.

Detection Strategy

For undirected graphs, the algorithm simplifies: no cross edges exist, and no explicit stack is needed. The key condition identifies vertices whose children cannot reach ancestors:

low[child] >= discovery[vertex]

The root node requires special handling: it qualifies only if it has more than one child in the DFS tree.

Implementation

void find_cut_vertices(int current, int parent = -1) {
    time_in[current] = low_point[current] = ++global_timer;
    int child_count = 0;
    
    for (int adjacent : adjacency[current]) {
        if (adjacent == parent) continue;
        
        if (!time_in[adjacent]) {
            ++child_count;
            find_cut_vertices(adjacent, current);
            low_point[current] = min(low_point[current], low_point[adjacent]);
            
            if (low_point[adjacent] >= time_in[current] && parent != -1) {
                is_cut_vertex[current] = true;
            }
        } else {
            low_point[current] = min(low_point[current], time_in[adjacent]);
        }
    }
    
    if (parent == -1 && child_count > 1) {
        is_cut_vertex[current] = true;
    }
}

Bridges

Concept

A bridge is a edge whose removal increases the number of connected components in an undirected graph. Bridges represent the most vulnerable connections in network infrastructure.

Detection Strategy

The condition for bridges is stricter: low[child] > discovery[vertex]. This ensures no alternative path exists between the child and the vertex. Since undirected graphs store each edge twice, the algorithm tracks the edge ID to avoid considering the parant edge as a back edge.

Implementation

void detect_bridges(int vertex, int incoming_edge) {
    entry_stamp[vertex] = low_stamp[vertex] = ++current_time;
    
    for (auto [next, edge_id] : edge_list[vertex]) {
        if (edge_id == incoming_edge) continue;
        
        if (!entry_stamp[next]) {
            detect_bridges(next, edge_id);
            low_stamp[vertex] = min(low_stamp[vertex], low_stamp[next]);
            
            if (low_stamp[next] > entry_stamp[vertex]) {
                bridge_flags[edge_id] = true;
            }
        } else {
            low_stamp[vertex] = min(low_stamp[vertex], entry_stamp[next]);
        }
    }
}

// Graph construction
for (int i = 1; i <= edge_count; ++i) {
    int u, v;
    cin >> u >> v;
    edge_list[u].push_back({v, i});
    edge_list[v].push_back({u, i});
}