Skip to content
Shadow Cipher

Articulation Point In Graph

#include <bits/stdc++.h> // Includes common standard libraries like iostream, vector, unordered_map, list, algorithm, etc.
using namespace std;     // Use the standard namespace.


// Recursive DFS function to find articulation points.
// 'node': Current node being visited.
// 'parent': Parent of the current node in the DFS tree (used to avoid going back immediately).
// 'timer': Global time counter for discovery and low-link values. Passed by reference to increment globally.
// 'disc': Discovery time array (disc[i] = time when node i was first visited).
// 'low': Low-link value array (low[i] = lowest discovery time reachable from node i or its subtree,
//        including back-edges to ancestors).
// 'result': Vector to store the identified articulation points (may contain duplicates, requires sorting+unique later).
// 'adjList': Adjacency list of the graph.
// 'visited': Boolean array to keep track of visited nodes.
void dfs(int node, int parent, int &timer, vector<int> &disc,
         vector<int> &low, vector<int> &result, unordered_map<int, list<int>> &adjList,
         vector<bool> &visited) {


    visited[node] = true;             // Mark current node as visited.
    disc[node] = low[node] = timer++; // Set discovery time and initial low-link value, then increment timer.
    int childCount = 0;               // Counter for children in the DFS tree, used for root case.


    // Iterate over all neighbors of the current node.
    for(auto neigh : adjList[node]) {
        // If the neighbor is the immediate parent, skip it.
        // This is crucial to avoid false back-edges and correctly count children.
        if(neigh == parent) {
            continue;
        }


        // Case 1: Neighbor is not visited. It's a forward edge to a child in the DFS tree.
        if(visited[neigh] == false) {
            childCount++; // Increment child count for the current node.
            // Recursively call DFS on the neighbor. 'node' becomes the parent for 'neigh'.
            dfs(neigh, node, timer, disc, low, result, adjList, visited);


            // After the recursive call returns (meaning 'neigh' and its subtree are processed):
            // Update the low-link value of the current node.
            // 'low[node]' is the minimum of its current 'low' value and 'low[neigh]'.
            // This means 'node' can reach whatever 'neigh' (and its subtree) can reach.
            low[node] = min(low[node], low[neigh]);


            // Articulation Point Condition (for non-root nodes):
            // If the lowest discovery time reachable from 'neigh' (or its subtree) is greater than
            // or equal to the discovery time of the current node 'node', AND 'node' is not the DFS root.
            // This means there's no back-edge from 'neigh's subtree to an ancestor of 'node'
            // (or to 'node' itself if it forms a cycle only through 'node').
            // Removing 'node' would disconnect 'neigh's subtree.
            if(low[neigh] >= disc[node] && parent != -1) {
                result.push_back(node); // Add 'node' to the list of articulation points.
            }
        } else {
            // Case 2: Neighbor is visited and is NOT the parent. It's a back-edge (or cross-edge to ancestor).
            // This means a cycle is detected. Update the low-link value of the current node.
            // 'low[node]' should be the minimum of its current 'low' value and the discovery time
            // of the visited neighbor (which is an ancestor or part of a cycle).
            low[node] = min(low[node], disc[neigh]);
        }
    }


    // Special Case: Checking for the Starting Node (Root of the DFS tree).
    // The root is an articulation point if it has more than one child in the DFS tree.
    // Its removal would disconnect these multiple subtrees.
    if(parent == -1 && childCount > 1) {
        result.push_back(node); // Add the root node if it's an articulation point.
    }
}


// Main function to find all articulation points (cut vertices) in an undirected graph.
// 'edges': List of edges in the graph. Each inner vector {u, v} represents an edge.
// 'n': Total number of nodes.
// 'm': Total number of edges.
// Returns a vector of integers, where each integer is an articulation point.
vector<int> cutVertex(vector<vector<int>> &edges, int n, int m) {
    // 1. Create Adjacency List for the graph.
    unordered_map<int, list<int>> adjList;
    for(int i = 0; i < m; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adjList[u].push_back(v); // Add edge u -- v.
        adjList[v].push_back(u); // Add edge v -- u (for undirected graph).
    }


    // 2. Initialize data structures for DFS and articulation point finding.
    int timer = 0;             // Global timer.
    int parent = -1;           // Initial parent for DFS root.


    vector<int> disc(n, -1);   // Discovery time array, initialized to -1.
    vector<int> low(n, -1);    // Low-link value array, initialized to -1.
    vector<bool> visited(n, false); // Visited array, initialized to false.
    vector<int> result;            // Vector to store articulation points.


    // 3. Iterate through all nodes to ensure all connected components are visited.
    for(int i = 0; i < n; i++) {
        // If a node is not visited, it's the root of a new DFS tree in a component.
        if(!visited[i]) {
            dfs(i, parent, timer, disc, low, result, adjList, visited);
        }
    }


    return result; // Return the list of articulation points (might contain duplicates).
}


// Main function for input/output.
int main() {
    vector<vector<int>> edges; // Stores input edges as {u, v}.
    int n, m;                 // 'n' for nodes, 'm' for edges.


    cout << "Enter the number of nodes : ";
    cin >> n;


    cout << "Enter the number of edges : ";
    cin >> m;


    cout << "Enter the edges (u v):" << endl;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;         // Read u and v.
        edges.push_back({u, v}); // Add edge to vector.
    }


    // Call cutVertex function to find articulation points.
    vector<int> answer_articulation_points = cutVertex(edges, n, m);


    // Sort and remove duplicates from the result (a common practice as a node might be added multiple times).
    sort(answer_articulation_points.begin(), answer_articulation_points.end());
    answer_articulation_points.erase(unique(answer_articulation_points.begin(), answer_articulation_points.end()), answer_articulation_points.end());


    cout << "Articulation Points : ";
    if (answer_articulation_points.empty()) {
        cout << "None"; // If no articulation points found.
    } else {
        for(int ap : answer_articulation_points) { // Iterate and print.
            cout << ap << " ";
        }
    }
    cout << endl;


    return 0; // Indicate successful execution.
}

1. Problem Statement

  • Goal: Identify all “articulation points” (also known as “cut vertices”) in a given undirected graph.
  • Articulation Point Definition: A vertex (node) in a connected graph whose removal (along with all incident edges) increases the number of connected components. In simpler terms, it’s a critical node that, if removed, would disconnect a part of the graph.
  • Input: List of edges (u, v), total n nodes, total m edges.
  • Output: A list of integers, where each integer represents an articulation point.

2. Core Idea (Tarjan’s Algorithm / DFS-based)

Similar to finding bridges, this algorithm uses a Depth-First Search (DFS) traversal and maintains two important arrays for each node:

  • disc[node] (Discovery Time): The time (or order) at which a node node was first visited during the DFS traversal.
  • low[node] (Lowest Ancestor Time): The lowest discovery time reachable from node (including node itself) through any path, including back-edges (edges to already visited ancestors).

The Articulation Point Conditions: A node u is an articulation point if:

  1. Case 1: u is the DFS root (i.e., parent == -1 for u in the dfs call)

    • And u has at least two independent children in the DFS tree (child > 1). Independent means their subtrees don’t share any common nodes other than u. If u is removed, these children and their subtrees would become disconnected from each other.

  2. Case 2: u is NOT the DFS root

    • And there exists at least one child v of u in the DFS tree such that low[v] >= disc[u].
    • This means that the subtree rooted at v (including v) cannot reach any ancestor of u (or u itself) without going through u. If u is removed, v and its entire subtree would become disconnected from the rest of the graph.

3. Algorithm Steps (cutVertex and dfs functions)

A. cutVertex Function (Main Wrapper)

  1. Build Adjacency List:

    • Create an adjList (unordered_map<int, list<int>>) from the input edges.
    • For each edge (u, v), add v to adjList[u] and u to adjList[v] (undirected graph).

  2. Initialize Data Structures:

    • timer = 0: A global counter for discovery times.
    • disc[n]: vector<int> initialized to -1. Stores discovery times.
    • low[n]: vector<int> initialized to -1. Stores lowest reachable ancestor times.
    • parent = -1: Special value for the parent of the initial DFS call’s root.
    • visited[n]: vector<bool> initialized to false. To track visited nodes.
    • result: vector<int> to store the identified articulation points. Note: For articulation points, it’s common to use a vector<bool> isArticulationPoint(n, false) to avoid duplicates if a node qualifies multiple times, then collect results. The current code adds duplicates.

  3. Initiate DFS for all components:

    • Loop through all nodes i from 0 to n-1.
    • If !visited[i], it means i is part of an unvisited component. Start DFS from i:
      • dfs(i, parent, timer, disc, low, result, adjList, visited);

  4. Return: The result vector containing all articulation points (may contain duplicates if a node qualifies multiple times). Sorting and removing duplicates is recommended.

B. dfs Function (Recursive Traversal)

  • Parameters: node (current node), parent (parent of node in DFS tree), timer, disc, low, result, adjList, visited.

  • Local Variable: int child = 0; (Counts the number of children in the DFS tree for the current node).

  • Base Actions (on entering node):

    1. visited[node] = true; (Mark current node as visited).
    2. disc[node] = low[node] = timer++; (Set discovery time and initial low-link value, then increment timer).

  • Explore Neighbors: For each neigh in adjList[node]:

    1. Skip Parent: if (neigh == parent) continue; (Crucial: avoids considering the edge back to the immediate parent).

    2. If neigh is NOT visited (visited[neigh] == false): (Forward edge to an unvisited child)

      • Increment child++;
      • Recursively call dfs(neigh, node, timer, disc, low, result, adjList, visited);
      • After recursive call returns (from child neigh):
        • low[node] = min(low[node], low[neigh]); (Update low[node] with low[neigh]. This means node can reach whatever neigh can reach).
        • Articulation Point Condition (Case 2): if (low[neigh] >= disc[node] && parent != -1):
          • If low[neigh] (lowest reachable discovery time from neigh’s subtree) is greater than or equal to disc[node] (discovery time of its parent node), and node is not the DFS root. This means neigh’s subtree (including neigh) cannot reach any node above node without passing through node. So, node is an articulation point.
          • result.push_back(node); (Add node to the result).

    3. If neigh IS visited (visited[neigh] == true): (Back edge to an already visited ancestor, or cross edge)

      • low[node] = min(low[node], disc[neigh]); (Update low[node] with disc[neigh]. This indicates that node can reach an already visited node (neigh) directly, which might be an ancestor and thus part of a cycle).

  • Special Case: Checking for Starting Node (DFS Root):

    • if (parent == -1 && child > 1):
      • After exploring all neighbors, if node was the root of the DFS tree (parent == -1), and it has more than one child in the DFS tree, then node is an articulation point. Its removal would disconnect its children’s subtrees.
      • result.push_back(node);

4. Time and Space Complexity

  • Time Complexity: O(V + E)
    • Building adjList: O(M).
    • DFS traversal: Each vertex and edge is visited exactly once. O(V + E).
    • Sorting result (in main): O(A log A) where A is number of articulation points (max V).
    • Total: O(V + E).
  • Space Complexity: O(V + E)
    • adjList: O(V + E).
    • disc, low, visited arrays: O(V).
    • Recursion stack for DFS: O(V) in worst case (skewed graph).
    • result vector: O(V) in worst case.

5. Key Points / Intuition

  • low[node] >= disc[parent] vs low[v] > disc[u]:

    • For articulation points, we use low[child] >= disc[current_node]. The equality low[child] == disc[current_node] means the child’s subtree can only reach up to current_node via a back-edge. If current_node is removed, this path is cut.
    • For bridges, we use low[child] > disc[current_node]. If low[child] is strictly greater, it means there’s no path from child’s subtree that bypasses current_node.

  • Handling DFS Root: The root of a DFS tree is an articulation point only if it has at least two children in the DFS tree. This is because removing the root would disconnect these children’s subtrees from each other. If it has only one child (or none), removing it just removes that branch, but doesn’t increase component count among other existing branches.