Graphs & Traversal

Contracting each strongly connected component to one node can never leave a cycle. A cycle through two component-nodes would make all their vertices mutually reachable, so those components would have been a single larger component — which maximality already forbids.

The vertex finishing last in the first pass lies in a source component nothing else reaches. Reversing every edge turns that source into a sink, so a traversal started there is trapped inside one component and cannot leak outward.

A node finishes only after every node it points to has finished, so the finishing sequence lists dependents first. Reversing it puts each node ahead of everything it points to; visit order gives no such guarantee.

Snapshot the queue size at the top of each pass and drain exactly that many nodes: that block is one layer, which answers how many hops. Recovering the route needs a stored discoverer per node, walked backwards from the target.

In depth-first search a vertex finishes only after everything below it has finished, so postorder emits the innermost items first — exactly what release requires. Preorder emits a container before its contents, which is acquisition order, not teardown order.

Kruskal's silently returns a minimum spanning forest: one optimal tree per component, with V minus c edges instead of V minus one. The planner must compare the accepted-edge count against V minus one and report the unreachable sites.

The total cost is O(V*E), because each of the V vertices triggers a full pass over the edge records. Bucketing the edges by source once, in O(V+E), turns the whole sweep into O(V+E).

At 400 stations the travel-time graph is dense, so 400 queue-driven searches cost more than one triple loop of roughly 64 million add-and-compare steps. The loop yields the same matrix and makes every later query an O(1) lookup.

When the two sides are distinct entity types — workers and shifts — every edge crosses and bipartiteness holds by construction. When edges relate peers, worker against worker, it is a property you must test, and it can fail.

A dependency graph admits many valid orders, so pin the choice: hold the ready set in a min-heap keyed on a canonical module identifier, and sort adjacency lists. Cost is a log factor on node pushes and pops.

Seed all k docks into the frontier at distance zero and run once: every floor cell's first discovery is its distance to the nearest dock. That is one O(V + E) pass instead of k passes plus a per-cell minimum fold.

Recursion depth in depth-first search grows with the size of the connected region being walked, not with the picture's dimensions, so one large region nests more frames than the call stack allows. Rewrite the traversal around an explicit stack.

Nothing about any single call. The bound is amortized over a whole sequence: m operations cost O(m alpha(n)) in total, while one individual lookup can still walk O(log n) links. Amortized here means worst-case sequence, not average input.

Accept it when the negative edges are part of the real cost model and the queries are few or offline. Deleting or flattening them makes the algorithm faster by answering a different question.

At that density both layouts are O(V^2), so constants decide. The matrix is 90,000 contiguous cells — a few kilobytes packed as bits — with no per-edge record overhead, direct O(1) pair tests and rows that stream through cache.

Rates compound by multiplying while route costs add, and profit means a product above one. Taking the logarithm turns the product into a sum, and negating turns "above one" into "below zero" — exactly a negative cycle.

Nothing breaks in the output: with non-negative weights the strict-improvement test rejects every update a stale pop could attempt. The damage is performance - each stale pop re-scans a settled vertex's whole adjacency list, and heap entries grow toward one per relaxation.

Pick any page as root. Traverse forward from it, then traverse from it with every link reversed. If both sweeps reach all ten million pages, the graph is strongly connected. Two linear passes, no decomposition needed.

The visited set breaks first. Generating neighbors stays cheap per state, but remembering a billion of them costs gigabytes even at eight bytes each, so the real decision is what you give up: memory, recomputation, exactness or scope.

Decide by direction of change. A cheaper edge patches in O(V^2); a closed aisle makes routes more expensive, has no cheap patch, and forces a rerun. Serve stale distances only where the error is bounded and visible.

A topological order is one serialisation, not a schedule. The floor on wall-clock time is the longest weighted path through the graph, and with W workers also total work divided by W. Act on whichever floor binds.

Union-find has no efficient split, so you design around it: keep merges undoable in reverse order with an undo log and no path flattening, or rebuild the affected component from stored evidence. Pick by retraction rate and component size.