Graphs

DEG — Degree Array

solved Problem statement

DDEG — Double-Degree Array

solved Problem statement

BFS — Breadth-First Search

solved Problem statement

CC — Connected Components

solved Problem statement

BIP — Testing Bipartiteness

solved Problem statement

DAG — Testing Acyclicity

solved Problem statement

DIJ — Dijkstra's Algorithm

solved Problem statement

SQ — Square in a Graph

solved Problem statement

BF — Bellman-Ford Algorithm

solved Problem statement

CTE — Shortest Cycle Through a Given Edge

solved Problem statement

TS — Topological Sorting

solved Problem statement

Any order with every edge pointing forwards is accepted, so that property is asserted rather than the sample text.

HDAG — Hamiltonian Path in DAG

solved Problem statement

Hard in general, easy on a DAG: a Hamiltonian path exists exactly when consecutive vertices of the topological order are joined by an edge.

NWC — Negative Weight Cycle

solved Problem statement

Every distance starts at 0, not just vertex 1, so a cycle unreachable from vertex 1 is still found.

SCC — Strongly Connected Components

solved Problem statement

Kosaraju, both passes iterative: a recursive depth-first search reads better but its depth is the length of a path, and the track allows 10^3 vertices.

2SAT — 2-Satisfiability

solved Problem statement

The hardest problem in the track and the one that pays off the rest: the implication graph is solved with the same Kosaraju pass SCC uses. Answers are checked by substituting them back into the formula, since any satisfying assignment is accepted.

GS — General Sink

solved Problem statement

SC — Semi-Connected Graph

solved Problem statement

SDAG — Shortest Paths in DAG

solved Problem statement

Relaxing once in topological order is linear, where Bellman-Ford needs n-1 rounds; acyclicity is what buys that.