DSA & Algorithms
Part 11 of 16 · DSA Advanced & Company FavoritesGraphs Advanced - SCC, Bridges, Articulation, Bipartite
Tarjan/Kosaraju SCC, bridges, articulation points, and bipartite coloring for advanced graph rounds.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You need components, bridges, or a 2-coloring
Prefer
Track discovery and low-link, or color the nodes
A bridge is an edge whose child cannot climb back.
- Tarjan or Kosaraju both yield SCCs.
- Articulation uses the root rule and the low rule.
- Odd cycle means not bipartite.
Alternative
Run plain visited DFS
Visited alone does not name a bridge or an SCC.
- You drop the parent edge and call every tree edge a bridge.
- You forget the second Kosaraju pass.
- You 2-color and skip a component.
Time the DFS, then read low
Bridges, articulation, SCC, bipartite.
- 1
Assign discovery times
The parent edge is not a back edge. - 2
Propagate low-link
A child that cannot climb marks a bridge. - 3
Color or transpose
2-color for bipartite. Second pass for Kosaraju.
Overview
Tarjan/Kosaraju SCC, bridges, articulation points, and bipartite coloring for advanced graph rounds.
When companies ask this
Recognition cues: critical connections; bipartite / is graph coloring; strongly connected components; articulation points.
Mental model
Flow
- 1
1. Record discovery time
- next2. Compute low-link
- 2
2. Compute low-link
- next3. Bridge or articulation point
- 3
3. Bridge or articulation point
- next4. Kosaraju or Tarjan SCCs
- 4
4. Kosaraju or Tarjan SCCs
- next5. 2-color to test bipartite
- 5
5. 2-color to test bipartite
Lesson map
Graphs Advanced - SCC, Bridges, Articulation, Bipartite
Tarjan/Kosaraju SCC, bridges, articulation points, and bipartite coloring for advanced graph rounds.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB dfs["1. Record discovery time"] low["2. Compute low-link"] bridge["3. Bridge or articulation point"] scc["4. Kosaraju or Tarjan SCCs"] dfs -->|1. Record discovery time| low low -->|2. Compute low-link| bridge bridge -->|3. Bridge or articulation point to| scc
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- All O(V+E). Bridge DFS raises
sys.setrecursionlimitbecause a long path can pass Python's default frame limit. The TypeScript BFS dequeues with a head index. - Pitfalls: bridge condition
>not≥; forgetting parent; directed vs undirected SCC.
Interviewer traps
LeetCode drill (real problems)
- Critical Connections in a Network
- Is Graph Bipartite
- Possible Bipartition
- Number of Provinces
- Redundant Connection
- Redundant Connection II
- Course Schedule
- Find Eventual Safe States
- Critical Edges / MST related
YouTube
Interview Q&A
Bridge condition?
Answer
low[v] > disc[u] on tree edge.
Bipartite?
Answer
2-color; odd cycle => no.
Kosaraju?
Answer
DFS finish order; DFS on transpose assign comps.
Tarjan SCC?
Answer
One DFS + stack + low-link.
Articulation root?
Answer
≥2 children in DFS tree.
Related wave-1?
Answer
graphs-dfs-bfs, union-find, topo.
Condensation?
Answer
Contract SCCs -> DAG.
2-SAT link?
Answer
Implication graph SCCs.