progress

~/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.

Graph structure

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.

esc