Biconnected Component

Core Concepts

Biconnected Component (BCC) — a maximal subgraph with no articulation point; equivalently, any two vertices in a BCC lie on a common simple cycle. A BCC contains at least one edge; an isolated vertex is not a BCC under standard definitions (some sources count degree-0 vertices as trivial BCCs — clarify in interviews).

2-Vertex-Connected (Biconnected) Graph — a connected graph that remains connected after removing any single vertex. BCCs partition the edges of a graph (edges belong to exactly one BCC; vertices can belong to multiple BCCs).

2-Edge-Connected Component — a maximal subgraph that remains connected after removing any single edge. Every 2-vertex-connected component is also 2-edge-connected, but not vice versa.

Articulation Point (Cut Vertex) — a vertex whose removal increases the number of connected components. Formally, v is a cut vertex iff removing v and all its incident edges disconnects the graph.

Bridge (Cut Edge) — an edge whose removal increases the number of connected components. Bridges are exactly the edges that do not lie on any simple cycle.

Low Value (low-link) — for a vertex v in a DFS tree, low[v] = minimum of disc[v], disc[w] for all back edges (v, w), and low[child] for all tree-edge children. Captures the earliest-reachable discovery time via the subtree rooted at v.

Discovery Time (disc) — the DFS visit order timestamp assigned to each vertex when first visited. Serves as a surrogate for DFS tree depth ordering.

DFS Tree — the spanning tree formed by tree edges during DFS. Back edges connect a descendant to an ancestor; in undirected graphs there are no cross or forward edges (only tree edges and back edges).

Block-Cut Tree (BC Tree) — a tree whose nodes are the BCCs and cut vertices of a graph, with an edge between a BCC node and a cut vertex node whenever the cut vertex belongs to that BCC. Encodes the articulation structure of the entire graph.

---

Types / Variants

---

Key Algorithms

Tarjan's Articulation Point Algorithm

Finds all cut vertices in an undirected graph in one DFS pass. Assigns disc[v] and low[v]; vertex v is a cut vertex if (a) v is the DFS root with ≥ 2 tree-edge children, or (b) v is not the DFS root and has a child c with low[c] >= disc[v]. Time O(V + E), space O(V).

The condition low[c] >= disc[v] means the subtree at c cannot reach any ancestor of v via a back edge — so cutting v disconnects c's subtree.

low[v] = disc[v] = timer[0]; timer[0] += 1
for c in adj[v]:
    if not visited[c]: low[v] = min(low[v], dfs(c, v))
    elif c != parent:  low[v] = min(low[v], disc[c])

Root case: count tree-edge children of root separately; root is a cut vertex iff children >= 2.

Tarjan's Bridge Algorithm

Finds all bridges in one DFS pass. An edge (v, c) (where c is a tree-edge child) is a bridge iff low[c] > disc[v]. The strict inequality (vs. >= for articulation points) distinguishes bridges from cut vertices. Time O(V + E), space O(V).

The key difference from articulation points: low[c] > disc[v] means c's entire subtree has no back edge reaching v or above — so the single edge (v, c) is the only path from c's subtree to the rest.

if low[c] > disc[v]:
    bridges.append((v, c))

Multi-edge caveat: in graphs with parallel edges, track by edge index rather than parent vertex; a back edge to parent is only a back edge if there is no parallel edge providing an alternative path.

Biconnected Component Extraction (Edge-Stack Method)

Maintains an explicit edge stack during DFS. When the condition low[c] >= disc[v] triggers (same as articulation point condition), pop all edges from the stack down to and including (v, c) — they form one BCC. Push each edge onto the stack before recursing into the child. Time O(V + E), space O(E) for the stack.

stack.append((v, c))   # push before recursing
# after dfs(c, v) returns:
if low[c] >= disc[v]:
    bcc = []
    while stack[-1] != (v, c): bcc.append(stack.pop())
    bcc.append(stack.pop())

Block-Cut Tree Construction

After finding all BCCs and cut vertices, build a bipartite tree: one node per BCC, one node per cut vertex, edges between a BCC node and each cut vertex it contains. The resulting structure is always a tree (or forest for disconnected graphs). Enables tree DP to answer questions about the original graph's connectivity structure. Time O(V + E) to build after BCCs are known.

Iterative DFS for Tarjan (Stack-Based)

The recursive Tarjan implementation hits Python's recursion limit for graphs with V > 1000. The iterative version uses an explicit stack storing (vertex, parent, adj_iterator_state). The key non-trivial step: simulate the post-order low update after all children are processed.

stack = [(root, -1, iter(adj[root]))]
while stack:
    v, par, it = stack[-1]
    c = next(it, None)
    if c is None: stack.pop(); # process post-order here

---

Advanced Techniques

Block-Cut Tree + Tree DP / LCA

What it solves: Problems asking for the minimum number of edges/vertices to add to make the graph 2-connected, counting paths between pairs of vertices that avoid a cut vertex, or finding the diameter of the "robust subgraph" structure.

Core mechanism: Contract each BCC to a single node; cut vertices remain as separate nodes. The resulting tree enables O(V) or O(V log V) tree DP and LCA queries that would be O(V²) on the original graph.

When to use over simpler alternatives: Only when the problem requires reasoning about the hierarchical relationship between BCCs (e.g., "how many BCCs lie on the path between nodes u and v?"). For simple bridge/articulation-point detection, the plain Tarjan pass is sufficient — don't build the full BC tree.

Complexity: O(V + E) to build; O(V log V) preprocessing for LCA; O(log V) per query.

2-Edge-Connected Component Condensation

What it solves: After identifying all bridges, condense each 2-edge-connected component (maximal subgraph with no bridge) into a single node. The resulting condensed graph is a tree (the "bridge tree"). Bridge-tree problems include: minimum edges to add to make graph bridgeless, path queries that count bridges crossed.

Core mechanism: Run Tarjan to mark bridges; then run DFS/BFS ignoring bridge edges to assign component IDs. Build the bridge tree from component IDs.

When to use: When the problem reduces to a tree problem after condensation — e.g., "minimum edges to add so no edge is a bridge" = ceil(leaf_count / 2) on the bridge tree, where leaf_count counts degree-1 nodes.

Complexity: O(V + E) condensation; then tree algorithms on a tree of size ≤ V.

Online/Incremental Biconnectivity

What it solves: Dynamically maintaining BCCs as edges are added (not deleted). Uses a link-cut tree or offline processing with Union-Find augmented with articulation tracking.

When to use over simpler alternatives: Only when edges arrive online and queries must be answered between insertions. For static graphs, plain Tarjan is always preferable. For fully offline edge sequences, sorting by insertion order and processing statically is usually simpler.

Complexity: O(log V) amortized per edge insertion with link-cut trees; O(α(V)) amortized with augmented Union-Find for simpler connectivity queries.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Parallel edges (multigraph): Tracking parent by vertex ID causes the parallel edge to be mistakenly counted as a back edge, inflating low values and missing bridges. Fix: track parent edge index, not parent vertex; only skip the exact edge used to arrive, not all edges to parent.

• Self-loops: A self-loop (v, v) should be ignored when computing low[v]; treating it as a back edge incorrectly sets low[v] = disc[v] which is already true, but the logic path can corrupt child-count tracking. Skip self-loops explicitly.

• Root vertex special case for articulation points: The low[c] >= disc[v] condition applied to the DFS root always triggers (since low[c] >= disc[root] for all children), giving false positives. The correct condition for root is children >= 2, not the low-value condition.

• Directed vs. undirected: Tarjan's BCC algorithm is for undirected graphs only. On directed graphs, "strongly connected components" (Tarjan SCC) is the analogous concept, but BCCs and SCCs are different algorithms. Applying undirected Tarjan to a directed graph silently produces wrong answers.

• Disconnected graphs: A single Tarjan DFS from one source misses other components. Always wrap in for v in range(n): if not visited[v]: dfs(v, -1).

• Single-edge BCCs: An edge that is a bridge forms its own BCC of size 2 (the two endpoints and the edge). This is a valid BCC — don't discard it or merge it with adjacent BCCs.

• Off-by-one in discovery time initialization: disc and low must be initialized to a sentinel (e.g., -1 or inf) before DFS. Using 0 as both the sentinel and the first valid timestamp causes the root to appear already-visited.

• Modifying adjacency list during DFS: Do not append reverse edges into the same adjacency list mid-DFS for undirected graphs; build the full list before running Tarjan.

• Block-cut tree on a 2-connected graph: If the graph is already biconnected, there are no cut vertices and the entire graph is one BCC — the block-cut tree is a single node with no cut vertex nodes. Handle this case explicitly to avoid an empty tree with indexing errors.

---

Implementation Notes

• Python's default recursion limit is 1000; use sys.setrecursionlimit(2 * n + 10) or convert to iterative DFS for any graph with V > 500 to avoid RecursionError.
• When building undirected adjacency lists, store edges as (neighbor, edge_index) tuples from the start if there is any chance of parallel edges — retrofitting index tracking is error-prone.
• low[v] should only be updated from back edges to ancestors (i.e., already fully or partially visited nodes), never from cross edges. In undirected DFS there are no cross edges, so any visited non-parent neighbor is an ancestor back edge — but verify this assumption when adapting code from directed-graph SCC implementations.
• The edge stack in BCC extraction stores edges as (u, v) tuples; when checking the stopping condition stack[-1] != (v, c), ensure canonical ordering (min, max) or store directed edges consistently to avoid tuple-comparison mismatches.
• disc and low arrays of size n require knowing n upfront; for online/streaming graphs, use dictionaries instead.
• For the block-cut tree, indexing BCCs and cut vertices in a single node namespace (BCCs first, then cut vertices, or vice versa) prevents off-by-one errors when building the bipartite adjacency list.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Bridges and Articulation Points (Fundamentals)

• LeetCode 1192 — Critical Connections in a Network (bridges; classic direct application)
• LeetCode 1568 — Minimum Number of Days to Disconnect Island (bridges on grid graph)
• LeetCode 2685 — Count the Number of Complete Components (BCC-adjacent; 2-vertex-connected check)

Articulation Points

• LeetCode 1489 — Find Critical and Pseudo-Critical Edges in MST (bridge-like reasoning in weighted graphs)
• Classic: "Server Network" — given N servers, find all servers that are single points of failure

Biconnected Components / Block-Cut Tree

• LeetCode 2801 — Count Stepping Numbers in Range (not BCC, but uses digit DP — verify tag)
• Classic competitive: "Cave system" — count how many BCCs contain a given vertex; answer is block-cut tree degree
• Classic: "Minimum edges to make graph 2-edge-connected" — bridge tree leaf count formula

Hard / Combined

• LeetCode 2360 — Longest Cycle in a Graph (directed; uses similar low-link intuition)
• Classic: "Road reconstruction" — offline dynamic bridge detection

Clarification Questions to Ask

• Are there parallel edges (multigraph) or self-loops? Changes the parent-skip logic.
• Is the graph directed or undirected? Biconnected components are an undirected-graph concept.
• Is the graph guaranteed to be connected, or can it be a forest/disconnected?
• What is the definition of "biconnected" used — vertex connectivity (2-vertex-connected) or edge connectivity (2-edge-connected)? They differ and interviewers sometimes conflate them.
• For grid graphs: are diagonal moves allowed? (affects bridge detection on implicit graphs)
• Do removed vertices also remove their incident edges? (yes, always — but confirm for unusual problem statements)

Common Interview Mistakes

• Applying the low[c] >= disc[v] articulation condition to the DFS root without the children-count special case, producing every non-leaf root as a false-positive cut vertex.
• Using strict > vs. >= incorrectly: bridges use low[c] > disc[v]; articulation points use low[c] >= disc[v]. Mixing them produces wrong answers with no compile error.
• Failing to handle multigraphs: tracking parent by vertex (not edge index) and counting a parallel edge as a back edge, which hides bridges.
• Building the BCC stack with vertices instead of edges, then incorrectly assigning vertices that appear in multiple BCCs to only one.
• Not running DFS from all unvisited sources, missing components in disconnected graphs.
• Conflating 2-vertex-connected and 2-edge-connected: a graph can have no bridges but still have articulation points (a vertex can be a cut vertex even if no single edge is a bridge).
• Recursion stack overflow on large inputs due to Python's 1000-frame limit when using recursive Tarjan.

Typical Follow-Up Escalations

• "Now find all biconnected components, not just articulation points." → Add an edge stack; pop edges when low[c] >= disc[v].
• "Now make the graph 2-connected with minimum edge additions." → Build the block-cut tree; answer = ceil(leaf_count / 2) where leaves are degree-1 BCC nodes.
• "The graph has up to 10^5 nodes — your recursive solution will stack overflow." → Convert to iterative DFS storing (v, parent, adj_iterator) on an explicit stack.
• "Now answer online queries: after adding each edge, is the graph still bridgeless?" → Link-cut tree for dynamic bridge maintenance, or offline sort + batch Tarjan.
• "What if edges have weights and we want the minimum-weight bridge?" → Run Tarjan to mark all bridges, then linear scan over bridges for minimum weight — O(E) additional.
• "Can a vertex be in more than one BCC?" → Yes — exactly the cut vertices appear in ≥ 2 BCCs. Non-cut vertices belong to exactly one BCC.