Bipartite check: 2-color the graph via BFS/DFS, fail if two adjacent nodes get the same color. Bridges and articulation points (Tarjan's low-link technique) find critical edges/nodes whose removal disconnects the graph.
Sub-patterns
- A — Bipartite Check. 2-color the graph; fail if two adjacent nodes match.
- B — Bridges & Articulation Points. Tarjan's low-link technique finds critical edges/nodes.
- C — Euler Paths. A path that uses every edge exactly once.
Practice set (4)
- Medium — Is Graph Bipartite?, Possible Bipartition
- Hard — Critical Connections in a Network, Reconstruct Itinerary
Pending
Bipartite Check
2-color the graph via BFS/DFS; fail as soon as two adjacent nodes get the same color.
Pending
Bridges & Articulation Points
Tarjan's low-link technique finds the critical edges and nodes whose removal disconnects the graph.
Pending
Euler Paths
Find a path that uses every edge of the graph exactly once.
Notes from readers
Comments — via GitHub