~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Strongly connected components
Kosaraju or Tarjan: groups where everyone reaches everyone; condense them into a DAG.
Notes
Recognise it when: a directed graph has cycles but you need DAG reasoning (longest path, reachability, "can everyone reach everyone?"), or you must group nodes that reach each other.
# Kosaraju: finish order on the graph, then sweep the reversed graph
order, seen = [], [False] * n
for s in range(n): # iterative DFS, push on finish
...
comp = [-1] * n
for s in reversed(order):
if comp[s] == -1: # BFS/DFS on the reversed graph labels one SCC
...
- Condensation: one node per component, an edge between components when any edge crosses; the result is a DAG, so topological-order DP works on it.
- Strongly connected? node 0 reaches everyone in the graph and in the reversed graph.
Gotchas: recursion depth on 10^5 nodes: write the DFS iteratively.
0 problems
No problems match those filters.