Graph Algorithms

Articulation Points & Bridges (Cut Vertices, Biconnected Components)

Table of Contents

Articulation points (cut vertices) and bridges (cut edges) identify single points of failure in a network. This guide covers Tarjan's algorithms in depth, biconnected components, and the block-cut tree.

Definitions and Motivation

Articulation Point (Cut Vertex)

A vertex in an undirected connected graph whose removal (along with all its incident edges) disconnects the graph, or more generally, increases the number of connected components.

Bridge (Cut Edge)

An edge in an undirected connected graph whose removal disconnects the graph, or more generally, increases the number of connected components.

Example Graph 0 1 2 3 4 5 6 AP: vertex 3 (thick border) Bridge: 1--3 (dashed) Removing vertex 3 splits {0,1,2} from {4,5,6}.

Why They Matter

  1. Network reliability: Bridges and APs are single points of failure.
  2. Infrastructure planning: Identify critical roads, power lines, or communication links.
  3. Algorithm building blocks: Biconnected components, 2-edge-connected components, and block-cut trees all build on these.
  4. Interview frequency: LeetCode 1192 (Critical Connections) is a classic Google problem.

DFS Tree Concepts

Understanding the DFS tree is the foundation for all bridge and AP algorithms.

Tree Edges vs Back Edges

When we run DFS on an undirected graph, every edge is classified as:

  • Tree edge: Edge (u, v) where v is unvisited when we explore from u. These form the DFS spanning tree.
  • Back edge: Edge (u, v) where v is already visited (an ancestor of u in the DFS tree). These create cycles.

Critical fact: In undirected DFS there are ONLY tree edges and back edges -- no cross edges or forward edges.

Original Graph A B C D E --> DFS Tree (root = A) A d=0 B d=1 D d=2 C d=3 E d=4 --- Tree edge Back edge

Discovery Time (disc[]) and Low Value (low[])

Discovery time disc[v] is the timestamp when DFS first visits vertex v.

Low value low[u] is the minimum discovery time reachable from the subtree rooted at u using tree edges followed by at most ONE back edge. Formally:

low[u] = min of:
  1. disc[u]                                    -- the vertex itself
  2. disc[w] for every back edge (u, w)          -- direct back edges
  3. low[v] for every child v in the DFS tree    -- inherited from children

Intuition: low[u] answers "how high up the DFS tree can u's subtree reach via a back edge?" If low[u] is small, u's subtree is well-connected to ancestors. If it cannot reach above u's parent, the edge to u might be a bridge.

Computing disc[] and low[]

DFS(u, parent):
    disc[u] = low[u] = timer++
    for each neighbor v of u:
        if v == parent:  skip (don't traverse parent edge)
        else if v not visited:
            DFS(v, u)                             // tree edge
            low[u] = min(low[u], low[v])          // inherit child's reach
        else:
            low[u] = min(low[u], disc[v])         // back edge to ancestor

Step-by-Step Example

0 1 2 3 4 5 
DFS from vertex 0:

Visit 0: disc[0]=0, low[0]=0
  -> 1 (tree): disc[1]=1, low[1]=1
      -> 3 (tree): disc[3]=2, low[3]=2
          See 0 (back): low[3] = min(2, disc[0]) = 0
      low[1] = min(1, low[3]=0) = 0
      -> 4 (tree): disc[4]=3, low[4]=3
          -> 5 (tree): disc[5]=4, low[5]=4
              -> 2 (tree): disc[2]=5, low[2]=5
                  See 1 (back): low[2] = min(5, disc[1]) = 1
              low[5] = min(4, low[2]=1) = 1
          low[4] = min(3, low[5]=1) = 1
      low[1] = min(0, low[4]=1) = 0
  low[0] = min(0, low[1]=0) = 0

Final:  disc[] = [0, 1, 5, 2, 3, 4]
        low[]  = [0, 0, 1, 0, 1, 1]

Finding Bridges -- Tarjan's Algorithm

The Key Insight

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]

Why? If low[v] > disc[u], no vertex in v's subtree can reach u or any ancestor of u through a back edge. The ONLY connection between v's subtree and the rest of the graph is edge (u, v). Removing it disconnects v's entire subtree.

If low[v] <= disc[u], some vertex in v's subtree has a back edge to u or above, providing an alternative path. Edge (u, v) is NOT a bridge.

BRIDGE: low[v] > disc[u] u disc=3 v low=4 BRIDGE no back edge up NOT BRIDGE: low[v] <= disc[u] u disc=3 v low=2 back edge anc

Complete C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class BridgeFinder {
    int n, timer = 0;
    vector<vector<int>> adj;
    vector<int> disc, low;
    vector<pair<int,int>> bridges;

    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        bool parentSkipped = false;
        for (int v : adj[u]) {
            if (v == parent && !parentSkipped) { parentSkipped = true; continue; } // skip parent edge once
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) {
                    bridges.push_back({u, v});
                }
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

public:
    BridgeFinder(int n) : n(n), adj(n), disc(n, -1), low(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<pair<int,int>> findBridges() {
        bridges.clear();
        fill(disc.begin(), disc.end(), -1);
        timer = 0;
        for (int i = 0; i < n; i++)
            if (disc[i] == -1) dfs(i, -1);
        return bridges;
    }
};

int main() {
    BridgeFinder bf(6);
    bf.addEdge(0, 1); bf.addEdge(0, 3); bf.addEdge(1, 3);
    bf.addEdge(1, 2); bf.addEdge(1, 4);
    bf.addEdge(4, 5); bf.addEdge(2, 5);

    for (auto [u, v] : bf.findBridges())
        cout << u << " -- " << v << endl;
    return 0;
}

Complexity: Time O(V + E), Space O(V + E).

Handling Parallel Edges (Multigraph)

The parent = -1 trick handles ONE duplicate edge. For true multigraphs, store edge indices:

void dfs(int u, int parentEdgeIdx) {
    disc[u] = low[u] = timer++;
    for (auto [v, eidx] : adj[u]) {
        if (eidx == parentEdgeIdx) continue; // skip same edge, not same vertex
        if (disc[v] == -1) {
            dfs(v, eidx);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) bridges.push_back({u, v});
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

Walkthrough: Finding Bridges

Find All Bridges 0 1 2 3 4 5 6 
DFS from 0:

Visit 0: d=0, l=0
  -> 1 (tree): d=1, l=1
    -> 5 (tree): d=2, l=2
      See 0 (back): l[5]=min(2,0)=0
    l[1]=min(1,0)=0. Bridge? l[5]=0 > d[1]=1? NO
    -> 2 (tree): d=3, l=3
      -> 3 (tree): d=4, l=4
        -> 6 (tree): d=5, l=5
          -> 4 (tree): d=6, l=6
            See 3 (back): l[4]=min(6,4)=4
          l[6]=min(5,4)=4. Bridge 6->4? l[4]=4 > d[6]=5? NO
        l[3]=min(4,4)=4. Bridge 3->6? l[6]=4 > d[3]=4? NO
      l[2]=min(3,4)=3. Bridge 2->3? l[3]=4 > d[2]=3? YES! Bridge: 2--3
    l[1]=min(0,3)=0. Bridge 1->2? l[2]=3 > d[1]=1? YES! Bridge: 1--2
  l[0]=min(0,0)=0. Bridge 0->1? l[1]=0 > d[0]=0? NO

Bridges: {1--2, 2--3}

Finding Articulation Points

The Key Insight -- Two Cases

Case 1: u is the root of the DFS tree. u is an AP iff it has 2+ children in the DFS tree.

Why? If root has one child, removing root leaves one connected subtree. With 2+ children, those subtrees are only connected through root.

Case 2: u is NOT the root. u is an AP if any child v satisfies:

low[v] >= disc[u]

Why? low[v] >= disc[u] means v's subtree cannot reach above u via back edges. Remove u, and v's subtree disconnects from u's ancestors.

Bridge vs AP condition: Bridges use > (strict), APs use >= (non-strict). If low[v] == disc[u], a back edge reaches u itself -- removing edge (u,v) is fine (v can still reach u), but removing vertex u disconnects v's subtree from ancestors.

Root: 2+ children R A B No cross-connection Non-root: low[v] >= disc[u] u disc=3 v low=3 v can only reach u, not above NOT AP: low[v] < disc[u] u disc=3 v low=1 back edge

Complete C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int n, timer_val = 0;
vector<vector<int>> adj;
vector<int> disc, low;
vector<bool> visited, isAP;

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = timer_val++;
    int children = 0;
    bool parentSkipped = false;

    for (int v : adj[u]) {
        if (v == parent && !parentSkipped) { parentSkipped = true; continue; }
        if (visited[v]) {
            low[u] = min(low[u], disc[v]); // back edge
        } else {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            // Non-root AP condition
            if (parent != -1 && low[v] >= disc[u])
                isAP[u] = true;
        }
    }
    // Root AP condition
    if (parent == -1 && children > 1)
        isAP[u] = true;
}

vector<int> findArticulationPoints(int numNodes) {
    n = numNodes;
    adj.assign(n, {});
    disc.assign(n, -1);
    low.assign(n, 0);
    visited.assign(n, false);
    isAP.assign(n, false);
    timer_val = 0;

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i, -1);

    vector<int> result;
    for (int i = 0; i < n; i++)
        if (isAP[i]) result.push_back(i);
    return result;
}

int main() {
    n = 7;
    adj.assign(n, {});
    disc.assign(n, -1);
    low.assign(n, 0);
    visited.assign(n, false);
    isAP.assign(n, false);

    auto addEdge = [](int u, int v) {
        adj[u].push_back(v); adj[v].push_back(u);
    };
    addEdge(0, 1); addEdge(0, 5); addEdge(1, 5); addEdge(1, 2);
    addEdge(2, 3); addEdge(3, 4); addEdge(3, 6); addEdge(4, 6);

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i, -1);

    cout << "Articulation Points: ";
    for (int i = 0; i < n; i++)
        if (isAP[i]) cout << i << " ";
    // Output: 1 2
    return 0;
}

Complexity: Time O(V + E), Space O(V + E).

Walkthrough

0 1 2 3 5 4 6 
DFS from 0 (root):

Visit 0: d=0, l=0, parent=-1 (root)
  -> 1: d=1, l=1
    -> 4: d=2, l=2
      See 0 (back): l[4]=min(2,0)=0
    l[1]=min(1,0)=0. AP? parent!=-1 && l[4]=0 >= d[1]=1? NO
    -> 2: d=3, l=3
      -> 3: d=4, l=4
        -> 5: d=5, l=5
          See 2 (back): l[5]=min(5,3)=3
        l[3]=min(4,3)=3. AP? l[5]=3 >= d[3]=4? NO
      l[2]=min(3,3)=3. AP? l[3]=3 >= d[2]=3? YES! Vertex 2 is AP
    l[1]=min(0,3)=0. AP? l[2]=3 >= d[1]=1? YES! Vertex 1 is AP
  l[0]=min(0,0)=0. Root check: children=1, NOT AP.

Result: APs = {1, 2}
  Remove 1: {0,4} disconnects from {2,3,5}. Confirmed.
  Remove 2: {0,1,4} disconnects from {3,5}. Confirmed.

Biconnected Components

Definition

A biconnected component (BCC) is a maximal subgraph with no articulation points. Equivalently, between any two vertices there exist at least two vertex-disjoint paths.

Key properties:

  • Every edge belongs to exactly one BCC.
  • Two BCCs share at most one vertex, which must be an articulation point.
  • A bridge (with its endpoints) forms its own BCC.
  • An AP can belong to multiple BCCs.
Biconnected Components BCC 1 0 1 2 BCC 2 3 BCC 3 4 5 6 7 AP: vertex 2 AP: vertex 3

Block-Cut Tree

The block-cut tree treats each BCC as a "block" node and each AP as a "cut" node, with edges between a block and each AP it contains. It is always a tree (or forest). Useful for connectivity queries after vertex removal.

Finding BCCs Using an Edge Stack

Extend the AP algorithm with an edge stack. When we identify a BCC boundary (low[v] >= disc[u]), pop edges until we pop (u, v).

#include <bits/stdc++.h>
using namespace std;

int n, timer_val = 0;
vector<vector<int>> adj;
vector<int> disc, low;
vector<bool> visited, isAP;
stack<pair<int,int>> stk;
vector<set<int>> bccSets;

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = timer_val++;
    int children = 0;

    for (int v : adj[u]) {
        if (v == parent) { parent = -1; continue; }
        if (!visited[v]) {
            children++;
            stk.push({u, v});
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if ((parent == -1 && children > 1) ||
                (parent != -1 && low[v] >= disc[u]))
                isAP[u] = true;

            // Extract BCC
            if (low[v] >= disc[u]) {
                set<int> comp;
                while (true) {
                    auto [a, b] = stk.top(); stk.pop();
                    comp.insert(a); comp.insert(b);
                    if (a == u && b == v) break;
                }
                bccSets.push_back(comp);
            }
        } else if (disc[v] < disc[u]) {
            stk.push({u, v});
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    n = 8;
    adj.assign(n, {});
    disc.assign(n, -1);
    low.assign(n, 0);
    visited.assign(n, false);
    isAP.assign(n, false);

    auto addEdge = [](int u, int v) {
        adj[u].push_back(v); adj[v].push_back(u);
    };
    addEdge(0,1); addEdge(1,2); addEdge(0,2); // triangle
    addEdge(2,3);                               // bridge
    addEdge(3,4); addEdge(4,5); addEdge(5,6); addEdge(6,3); // cycle

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i, -1);

    cout << "BCCs: " << bccSets.size() << endl;
    for (int i = 0; i < (int)bccSets.size(); i++) {
        cout << "  BCC " << i << ": { ";
        for (int v : bccSets[i]) cout << v << " ";
        cout << "}" << endl;
    }
    cout << "APs: ";
    for (int i = 0; i < n; i++) if (isAP[i]) cout << i << " ";
    cout << endl;
    return 0;
}

Complexity: Time O(V + E), Space O(V + E).

Building the Block-Cut Tree

#include <bits/stdc++.h>
using namespace std;

// After computing bccSets and isAP (from above), build block-cut tree:
// Nodes 0..numBCCs-1 are block nodes; numBCCs..numBCCs+numAPs-1 are cut nodes.

void buildBlockCutTree(int n, vector<set<int>>& bccSets, vector<bool>& isAP) {
    int numBlocks = bccSets.size();
    map<int, int> apToNode;
    int nextId = numBlocks;
    for (int i = 0; i < n; i++)
        if (isAP[i]) apToNode[i] = nextId++;

    int treeSize = nextId;
    vector<vector<int>> tree(treeSize);

    for (int b = 0; b < numBlocks; b++) {
        for (int v : bccSets[b]) {
            if (isAP[v]) {
                tree[b].push_back(apToNode[v]);
                tree[apToNode[v]].push_back(b);
            }
        }
    }
    // tree[] is now the block-cut tree adjacency list
    cout << "Block-cut tree has " << treeSize << " nodes ("
         << numBlocks << " blocks + " << (treeSize - numBlocks) << " APs)" << endl;
}

Edge Connectivity and Vertex Connectivity

Definitions

  • Edge connectivity (lambda): Minimum edges whose removal disconnects the graph.
  • Vertex connectivity (kappa): Minimum vertices whose removal disconnects it.
Connectivity Summary Property Meaning Equivalent to Has a bridge lambda = 1 Not 2-edge-connected Has an AP kappa = 1 Not biconnected No bridges, no APs kappa >= 2, lambda >= 2 Biconnected

Whitney's Theorem

kappa(G) <= lambda(G) <= delta(G)

Vertex connectivity <= Edge connectivity <= Minimum degree. A biconnected graph (no APs) is always 2-edge-connected (no bridges), but not vice versa.

For general lambda/kappa, use max-flow. For the special case of identifying bridges (lambda=1 edges) or APs (kappa=1 vertices), Tarjan's O(V+E) algorithm is optimal.

Classic Problems with Full Solutions

Problem 1: Critical Connections in a Network (LeetCode 1192)

Problem: Return all critical connections (bridges) in a network of n servers.

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int timer = 0;
    vector<vector<int>> adj;
    vector<int> disc, low;
    vector<vector<int>> result;

    void dfs(int u, int parent) {
        disc[u] = low[u] = timer++;
        for (int v : adj[u]) {
            if (v == parent) { parent = -1; continue; }
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u])
                    result.push_back({u, v});
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        adj.assign(n, {});
        disc.assign(n, -1);
        low.assign(n, 0);
        for (auto& c : connections) {
            adj[c[0]].push_back(c[1]);
            adj[c[1]].push_back(c[0]);
        }
        dfs(0, -1);
        return result;
    }
};

Complexity: Time O(V + E), Space O(V + E). Direct application of Tarjan's bridge algorithm.

Problem 2: Connected Components After Removing Each Vertex

Problem: For each vertex v in a connected graph, determine how many connected components remain if v is removed.

Approach: During AP computation, count how many children v have with low[child] >= disc[v]. Each such child's subtree becomes a separate component when v is removed.

#include <bits/stdc++.h>
using namespace std;

int n, timer_val = 0;
vector<vector<int>> adj;
vector<int> disc, low, compAfterRemoval;
vector<bool> visited;

void dfs(int u, int parent, bool isRoot) {
    visited[u] = true;
    disc[u] = low[u] = timer_val++;
    int children = 0, splits = 0;

    for (int v : adj[u]) {
        if (v == parent) { parent = -1; continue; }
        if (!visited[v]) {
            children++;
            dfs(v, u, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) splits++;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    // Root: each DFS child becomes separate component
    // Non-root: splits subtrees disconnect, rest stays as 1
    compAfterRemoval[u] = isRoot ? children : splits + 1;
}

int main() {
    n = 6;
    adj.assign(n, {});
    auto addEdge = [](int u, int v) {
        adj[u].push_back(v); adj[v].push_back(u);
    };
    addEdge(0,1); addEdge(1,2); addEdge(0,2); // triangle
    addEdge(2,3); addEdge(3,4); addEdge(4,5); addEdge(3,5); // cycle

    disc.assign(n, -1); low.assign(n, 0);
    visited.assign(n, false); compAfterRemoval.assign(n, 1);

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i, -1, true);

    for (int i = 0; i < n; i++)
        cout << "Remove " << i << ": " << compAfterRemoval[i] << " component(s)\n";
    // Remove 0: 1, Remove 1: 1, Remove 2: 2 (AP),
    // Remove 3: 2 (AP), Remove 4: 1, Remove 5: 1
    return 0;
}

Complexity: Time O(V + E), Space O(V).

Problem 3: Bridge Finding with Disrupted Traffic

Problem: For each bridge, compute how many node-pairs lose connectivity (product of the two resulting component sizes).

#include <bits/stdc++.h>
using namespace std;

int n, timer_val = 0;
vector<vector<int>> adj;
vector<int> disc, low, subSize;
vector<bool> visited;
vector<tuple<int,int,long long>> bridgeInfo;

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = timer_val++;
    subSize[u] = 1;

    for (int v : adj[u]) {
        if (v == parent) { parent = -1; continue; }
        if (!visited[v]) {
            dfs(v, u);
            subSize[u] += subSize[v];
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                long long disrupted = (long long)subSize[v] * (n - subSize[v]);
                bridgeInfo.push_back({u, v, disrupted});
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    n = 6;
    adj.assign(n, {}); disc.assign(n, -1); low.assign(n, 0);
    subSize.assign(n, 0); visited.assign(n, false);
    auto addEdge = [](int u, int v) {
        adj[u].push_back(v); adj[v].push_back(u);
    };
    addEdge(0,1); addEdge(1,2); addEdge(0,2); // triangle
    addEdge(2,3);                               // bridge
    addEdge(3,4); addEdge(4,5); addEdge(3,5); // triangle

    for (int i = 0; i < n; i++)
        if (!visited[i]) dfs(i, -1);

    for (auto [u, v, d] : bridgeInfo)
        cout << u << "--" << v << ": " << d << " pairs disrupted\n";
    // 2--3: 9 pairs (3 * 3)
    return 0;
}

Complexity: Time O(V + E), Space O(V + E).

Problem 4: Biconnected Components Decomposition

Problem: Decompose a graph into BCCs and identify which BCCs each AP belongs to.

Full solution provided in the Biconnected Components section above. The key idea: maintain an edge stack, pop edges when low[v] >= disc[u] to extract each BCC. An AP is any vertex appearing in 2+ BCCs.

Problem 5: Making a Graph 2-Edge-Connected

Problem: Find the minimum number of edges to add so a connected graph has no bridges.

Key Insight: Build the "bridge tree" by contracting each 2-edge-connected component into a single node. The result is a tree. Answer = ceil(L / 2) where L = number of leaves.

Why? Each leaf has exactly one bridge. Pairing leaves and adding edges between them eliminates two bridges per edge added.

Original 0 1 2 3 4 5 6 --> Bridge Tree A B C Leaves=2, Answer=ceil(2/2)=1 
#include <bits/stdc++.h>
using namespace std;

class MakeTwoEdgeConnected {
    int n, timer_val = 0;
    vector<vector<pair<int,int>>> adj; // (neighbor, edge_index)
    vector<int> disc, low, comp;
    vector<bool> visited, isBridge;

    void dfs(int u, int parentEdge) {
        visited[u] = true;
        disc[u] = low[u] = timer_val++;
        for (auto [v, eidx] : adj[u]) {
            if (eidx == parentEdge) continue;
            if (!visited[v]) {
                dfs(v, eidx);
                low[u] = min(low[u], low[v]);
                if (low[v] > disc[u]) isBridge[eidx] = true;
            } else {
                low[u] = min(low[u], disc[v]);
            }
        }
    }

    void label(int u, int id) {
        comp[u] = id;
        for (auto [v, eidx] : adj[u])
            if (comp[v] == -1 && !isBridge[eidx]) label(v, id);
    }

public:
    int solve(int numNodes, vector<pair<int,int>>& edges) {
        n = numNodes;
        int m = edges.size();
        adj.assign(n, {}); disc.assign(n, -1); low.assign(n, 0);
        visited.assign(n, false); isBridge.assign(m, false); comp.assign(n, -1);

        for (int i = 0; i < m; i++) {
            adj[edges[i].first].push_back({edges[i].second, i});
            adj[edges[i].second].push_back({edges[i].first, i});
        }

        for (int i = 0; i < n; i++)
            if (!visited[i]) dfs(i, -1);

        int numComps = 0;
        for (int i = 0; i < n; i++)
            if (comp[i] == -1) label(i, numComps++);

        if (numComps == 1) return 0;

        vector<int> degree(numComps, 0);
        for (int i = 0; i < m; i++)
            if (isBridge[i]) {
                degree[comp[edges[i].first]]++;
                degree[comp[edges[i].second]]++;
            }

        int leaves = 0;
        for (int i = 0; i < numComps; i++)
            if (degree[i] == 1) leaves++;

        return (leaves + 1) / 2;
    }
};

int main() {
    int n = 7;
    vector<pair<int,int>> edges = {
        {0,1},{1,2},{0,2}, {2,3}, {3,4},{4,5},{3,5}, {5,6}
    };
    MakeTwoEdgeConnected solver;
    cout << "Min edges to add: " << solver.solve(n, edges) << endl;
    // Bridge tree: [0,1,2]--[3,4,5]--[6], leaves=2, answer=1
    return 0;
}

Complexity: Time O(V + E), Space O(V + E).

Common Mistakes and Interview Tips

Mistake 1: Using >= for Bridges Instead of >

// WRONG: marks too many edges as bridges
if (low[v] >= disc[u]) bridges.push_back({u, v});

// CORRECT: strict inequality for bridges
if (low[v] > disc[u]) bridges.push_back({u, v});

If low[v] == disc[u], a back edge reaches u itself, so edge (u,v) is NOT a bridge.

Mistake 2: Forgetting the Root Case for APs

The root is an AP only if it has 2+ DFS children. The low[v] >= disc[u] condition is always true for the root (since disc[root]=0), so it must be handled separately:

if (parent == -1 && children > 1) isAP[u] = true;  // root case

Mistake 3: Skipping ALL Parent Edges

// WRONG: skips ALL edges to parent (breaks with parallel edges)
if (v == parent) continue;

// CORRECT: skip only once
if (v == parent) { parent = -1; continue; }

// BEST: use edge indices for multigraphs
if (edgeIdx == parentEdgeIdx) continue;

Mistake 4: Using low[v] Instead of disc[v] for Back Edges

// WRONG (can cause subtle bugs with APs)
if (visited[v]) low[u] = min(low[u], low[v]);

// CORRECT
if (visited[v]) low[u] = min(low[u], disc[v]);

For back edges, use disc[v], not low[v]. Using low[v] can propagate reachability information across different subtrees incorrectly. (Note: for bridges alone, low[v] happens to work, but always use disc[v] for correctness.)

Mistake 5: Forgetting Disconnected Graphs

// MUST loop over all vertices:
for (int i = 0; i < n; i++)
    if (!visited[i]) dfs(i, -1);

Mistake 6: Confusing BCCs with 2-Edge-Connected Components

BCC vs 2-ECC Property BCC 2-ECC Removes Vertices (APs) Edges (bridges) Vertex overlap Can share APs Disjoint partition

Interview Tips

  1. Start with definitions: Clearly define APs and bridges before coding.
  2. Draw the DFS tree: Explain tree/back edges, disc[], low[] on a diagram.
  3. State conditions explicitly: Bridge uses >, AP uses >=, root has separate logic.
  4. Know the complexity: O(V + E) for all Tarjan-based algorithms.
  5. Know when to use decomposition: Bridge tree for 2-edge problems, block-cut tree for 2-vertex problems. Many hard problems reduce to tree problems after decomposition.
  6. Mention edge cases: single vertex, tree (all edges are bridges), complete graph (no bridges/APs), disconnected graphs, parallel edges.

Summary Cheat Sheet

ARTICULATION POINTS & BRIDGES CHEAT SHEET Bridges (Cut Edges) Condition: low[v] > disc[u] (strict inequality) Meaning: v's subtree has NO back edge to u or above. Time: O(V + E) Articulation Points (Cut Vertices) Non-root: low[v] >= disc[u] (non-strict inequality) Root: children > 1 (2+ DFS tree children). Time: O(V + E) Biconnected Components Maximal 2-vertex-connected subgraphs. Edge stack + pop on low[v]>=disc[u]. Key Reminders Undirected DFS: only tree edges and back edges (no cross/forward) For back edges: update low[u] = min(low[u], disc[v]), NOT low[v]