5 subtopics · 16 problems
Graph Algorithms
Cycle detection, topological sort, bridges, articulation points, and strongly connected components.
01Cycle Detection
Detect cycles in directed and undirected graphs.
2 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1900CAnji's Binary Tree | medium | Solve |
| 1144FGraph Without Long Directed Paths | medium | Solve |
| 1904DSet To Max | hard | Solve |
| 1837EPlayoff Fixing | hard | Solve |
02Topological Sort
Order vertices of a DAG such that every edge goes left-to-right.
3 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1851DPrefix Permutation Sums | medium | Solve |
| 1881EBlock Sequence | medium | Solve |
| 1144FGraph Without Long Directed Paths | medium | Solve |
| 1837DBracket Coloring | hard | Solve |
03Bridges & Articulation Points
Find edges/vertices whose removal disconnects the graph.
3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 118EBertown roads | hard | Solve |
| 652EPursuit For Artifacts | hard | Solve |
| 732FTourist Reform | hard | Solve |
04Strongly Connected Components (SCC)
Kosaraju's or Tarjan's algorithm for directed graphs.
1 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 427CCheckposts | medium | Solve |
| 732FTourist Reform | hard | Solve |
| 894ERalph and Mushrooms | hard | Solve |
052-SAT
Solve boolean satisfiability with at most 2 literals per clause via SCC.
1 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 228EThe Road to Berland is Paved with Good Intentions | medium | Solve |
| 776DThe Door Problem | hard | Solve |
Was this helpful?