G-56: Articulation Point in Graph

An Articulation Point (or cut vertex) is any vertex in a connected graph whose removal—along with all its incident edges—increases the number of connected components in the graph. Understanding articulation points is crucial for analyzing network vulnerability, identifying single points of failure in distributed systems or computer networks, and understanding structural bottlenecks.

1. Why Do We Need Articulation Points? (Problem Statement)

• Single Points of Failure: In networking, telecommunications, or social network analysis, a bridge or an articulation point represents a critical node. If that node fails or is removed, the network partitions into isolated sub-networks.
• Distinction from Bridges:
  • A Bridge is an edge whose removal disconnects the graph.
  • An Articulation Point is a node (and all its attached edges) whose removal disconnects the graph.
• Status Quo Check: While simple degree-based heuristics (like removing a node with high degree) might suggest critical nodes, only depth-first search (DFS) tree property analysis guarantees finding all exact cut vertices in $O(V + E)$ time.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: City Intersections and Toll Plazas

Imagine a province where cities (nodes) are connected by highways (edges).

• If City $X$ is an articulation point, it acts as the sole gateway between Province A and Province B. If City $X$ is closed due to a natural disaster, citizens in Province A can no longer drive to Province B; the road network splits into disjoint components.
• If an ordinary city $Y$ is closed, alternate routes still exist through neighboring cities, keeping the road network fully connected.

3. Prerequisite: Building on "Bridges in a Graph"

This lecture directly builds upon the concepts established in G-55: Bridges in a Graph.

• Time of Insertion (tin): The timer counter value when a node is first visited during the DFS traversal.
• Lowest Time of Insertion (low): The lowest tin reachable from the current node using back-edges or tree-edges.
• Key Conceptual Difference from Bridges:
  • In Bridges, we checked if a back-edge could reach at or before the parent node (low[it] > tin[node]).
  • In Articulation Points, because we are removing an entire node (not just an edge), the descendant must be able to reach strictly before the current node (low[it] >= tin[node]). If it can only reach at the current node, removing that node traps the descendant, meaning the graph breaks.

4. The Articulation Point Condition & Edge Cases

The Standard DFS Condition

For any non-root node (i.e., parent != -1), if during DFS back-tracking from an adjacent node it, we find:

This implies that the subtree rooted at it has no back-edges connecting to any ancestor of node. Thus, removing node will isolate the subtree rooted at it, making node an Articulation Point.

The Root Node Exception (parent == -1)

The standard condition low[it] >= tin[node] fails for the starting DFS root node.

• Why? The root node has no parent. Even if all its subtrees have back-edges among themselves, the root itself cannot be evaluated by checking ancestors above it (since none exist).
• Correct Root Logic: The root node is an articulation point if and only if it has two or more independent children in the DFS tree. If it has $\ge 2$ children, removing the root splits those separate DFS subtrees apart.

5. Handling Visited Nodes and Back-Edges (The Subtle Trap)

When updating the low array for an adjacent node it:

1. If it is the parent: Skip updating low via the parent.
2. If it is already visited (Back-Edge):
   • Do NOT take low[it].
   • DO take tin[it] (low[node] = min(low[node], tin[it])).

Why use tin[it] instead of low[it] for visited nodes?

If we propagated low values greedily through already visited nodes (like in Bridges), a back-edge pointing to an ancestor via a visited path could falsely propagate reachability past a node that is about to be removed. By taking strictly tin[it] for visited nodes, we ensure that back-edges only register valid, independent alternate paths.

6. Complete Algorithm Workflow Walkthrough

Here is the structural execution flow for finding all articulation points:

7. Complete Production-Grade C++ Implementation

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

using namespace std;

class Solution {
private:
    int timer = 0;
    
    void dfs(int node, int parent, vector<int>& vis, vector<int>& tin, 
             vector<int>& low, vector<int>& mark, vector<vector<int>>& adj) {
        vis[node] = 1;
        tin[node] = low[node] = timer++;
        int child_count = 0;
        
        for (auto it : adj[node]) {
            if (it == parent) continue;
            
            if (vis[it]) {
                // Back-edge case: use tin instead of low
                low[node] = min(low[node], tin[it]);
            } else {
                // Forward edge in DFS tree
                dfs(it, node, vis, tin, low, mark, adj);
                low[node] = min(low[node], low[it]);
                
                // Condition for non-root articulation point
                if (low[it] >= tin[node] && parent != -1) {
                    mark[node] = 1;
                }
                child_count++;
            }
        }
        
        // Condition for root articulation point
        if (parent == -1 && child_count > 1) {
            mark[node] = 1;
        }
    }

public:
    vector<int> articulationPoints(int n, vector<vector<int>>& adj) {
        vector<int> vis(n, 0);
        vector<int> tin(n, -1);
        vector<int> low(n, -1);
        vector<int> mark(n, 0);
        
        // Traverse all components of the graph
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i, -1, vis, tin, low, mark, adj);
            }
        }
        
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (mark[i] == 1) {
                ans.push_back(i);
            }
        }
        
        if (ans.empty()) {
            return {-1};
        }
        return ans;
    }
};

int main() {
    int n = 5;
    vector<vector<int>> adj(n);
    // Example graph setup: 0-1, 1-2, 2-0, 0-3, 3-4
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    
    addEdge(0, 1);
    addEdge(1, 2);
    addEdge(2, 0);
    addEdge(0, 3);
    addEdge(3, 4);
    
    Solution obj;
    vector<int> points = obj.articulationPoints(n, adj);
    
    cout << "Articulation Points: ";
    for (int node : points) {
        cout << node << " ";
    }
    cout << endl;
    
    return 0;
}

8. Complexity Analysis

Summary and Key Takeaways

• Definition: An articulation point is a vertex whose removal increases the number of connected components in an undirected graph.
• Core Inequality: For any non-root node, the condition $\text{low}[it] \ge \text{tin}[\text{node}]$ identifies whether a descendant has zero back-edges leading to any proper ancestor of node.
• Root Node Special Rule: The starting DFS root cannot use the standard inequality formula; instead, it is an articulation point if and only if it has more than one independent child ($\text{child\_count} > 1$).
• Visited Node Handling: When encountering an already visited node that is not the parent, update low[node] using tin[it], never low[it], to prevent flawed greedy propagation through visited paths.
• Duplicate Prevention: Use a hash/marking array (mark) to flag vertices during traversal rather than printing or storing them instantly, preventing duplicate entries when multiple subtrees trigger the same articulation point.
• Fallback Behavior: If a graph contains no articulation points, the standard convention requires returning a vector containing [-1].