Graphs -> Bridges, Articulation, And BCC

Low-link structure in undirected graphs: critical edges, critical vertices, and block-cut style decomposition.

• Topic slug: graphs/bridges-articulation
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 4
• Curated external problems: 5

Microtopics

• low-link
• bridge
• articulation
• two-edge-connected
• block-cut-tree
• biconnected-component

Learning Sources

Source	Type
cp-algorithms bridges	Reference
cp-algorithms articulation points	Reference
USACO Guide BCCs and 2CCs	Reference
OI Wiki biconnected components	Reference

Practice Sources

Source	Type
CSES Problem Set	Practice
Library Checker Two-Edge-Connected Components	Practice
USACO contest archive	Practice

Repo Companion Material

Material	Type
Low-Link hot sheet	quick reference
Low-Link starter route	starter route
Necessary Roads note	anchor note
Graph cheatsheet	quick reference

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Necessary Cities	CSES	Medium	Low-Link	Low-Link DFS; Root Special Case; Critical Vertex Output	DFS; Undirected Graphs; Low-Link Inequalities	Critical Vertices; Root Case; Cut Vertices	The matching articulation-point counterpart to Necessary Roads.
Necessary Roads	CSES	Medium	Low-Link	Low-Link DFS; Bridge Detection; Critical Edge Output	DFS; Undirected Graphs; Entry Times	Critical Edges; DFS Tree; Bridge Detection	The cleanest bridge-only contest problem for learning the strict low-link inequality.

Practice

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Two-Edge-Connected Components	Library Checker	Medium	Two-Edge-Connected Components	Bridge Removal; Component Compression; Tree Of Components	Bridge Detection; DFS; Connected Components	Bridge Compression; 2-Edge Connectivity	A direct verifier once bridges themselves are trusted and you want the compression layer.

Classics

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Submerging Islands	SPOJ	Medium	Classic	Low-Link DFS; Cut Vertex Counting; Root Handling	DFS; Undirected Graphs; Low-Link	Cut Vertices; Articulation Points	A classic articulation-point problem where the root case and repeated reporting both matter.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Forbidden Cities	CSES	Hard	Bcc, Block-Cut Tree	Block-Cut Tree; LCA On Reduced Structure; Query Reduction	Articulation Points; Trees; LCA	Vertex-Biconnected Components	The strongest practical reason to go beyond plain articulation points into full block-cut structure.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
NECESSARYROADS	Necessary Roads	primary	medium	low-link; bridge detection; dfs tree critical edge	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py