Advanced Graphs

Advanced graph questions usually combine traversal with an extra invariant: distance, low-link value, bitmask state, safe/unsafe status, or component impact. The interview move is to name both the graph model and the extra state you carry.

Mental Model

• Weighted routing: Dijkstra or minimax path when edge cost matters.
• Structure discovery: Tarjan-style low-link values find bridges or articulation behavior.
• State graph: the node is not just a vertex; it can be (vertex, mask), (stop, bus line), or another expanded state.
• Reverse reasoning: start from terminal/safe states or infection sources when forward simulation repeats work.

Diagram

Problem List

Start with 1192. Critical Connections, 1631. Path With Minimum Effort, 815. Bus Routes, and 847. Shortest Path Visiting All Nodes.