Graph Algorithms Beyond Traversal

A cable network, a dependency cycle, and a job assignment can all be drawn as graphs. They ask different questions: which edges should we buy, which vertices are mutually reachable, and which assignments can coexist? A traversal visits vertices; these problems require an additional invariant.

Before starting, you should be able to run DFS with a visited set, interpret an adjacency list, and use union-find. Revisit the Union-Find module if find and union are unfamiliar. Work through the three sections in exercise order. By the end, you should be able to justify a selected edge, reproduce the two SCC passes, and repair a matching by rerouting assignments.

1. Minimum spanning tree: connect components cheaply

The MST exercise gives a connected, weighted, undirected graph. A spanning tree uses exactly n-1 edges, reaches every vertex, and has no cycle. We minimize the sum of those edges, not the distance from one source to every destination. Negative edge weights are allowed; unlike Dijkstra, Kruskal does not require nonnegative weights.

Kruskal maintains a forest whose components are represented by a disjoint-set structure:

1. Sort all edges by nondecreasing weight.
2. For edge (u,v,w), compare find(u) and find(v).
3. If the roots differ, join them, add w to the total, and increment the selected-edge count. Otherwise skip the edge: its endpoints are already connected by a path, so adding it would make a cycle.
4. Stop after selecting n-1 edges. A single vertex needs zero edges and has weight zero.

Trace four vertices with edges AB:-2, AC:1, BC:1, CD:4, BD:7. Process the equal-weight edges in the displayed order:

Edge	Components before decision	Decision	Total
AB, -2	A / B / C / D	Join A and B	-2
AC, 1	AB / C / D	Join AB and C	-1
BC, 1	ABC / D	Skip the cycle	-1
CD, 4	ABC / D	Join ABC and D	3

Why is the cheap crossing edge safe? Take a minimum spanning tree compatible with earlier choices. If it lacks the new edge, adding that edge creates a cycle. The cycle must contain another edge crossing the same component boundary. That edge cannot be cheaper than the one currently selected; replace it without increasing the total. This exchange keeps at least one optimum compatible with every accepted edge. Ties may produce different trees with the same weight.

Sorting costs O(E log E); union-find with rank and path compression adds amortized O(E α(V)). Use a 64-bit accumulator: up to n-1 weights may be summed. The exercise promises connectivity; a generalized API would need to specify an error or a minimum spanning forest when fewer than n-1 edges can be selected.

Pause and predict: in the trace, accepting BC would make the total look smaller than waiting for CD. Why is it still wrong? It creates a cycle and leaves D unreachable. Total weight alone does not certify a spanning tree.

2. SCCs: traversal order determines the answer

A strongly connected component is a maximal group of vertices with directed paths both ways between every pair. A lone vertex is an SCC even without a self-loop. Replacing each SCC by one vertex produces a DAG: a directed cycle among components would make them one larger SCC.

Use this exact Kosaraju convention in the exercise:

1. DFS on the original graph from every unvisited vertex. Append a vertex to finish only after all its outgoing neighbors are processed.
2. Reverse every edge and clear the visited/assigned state.
3. Visit starting vertices in reverse finish order. Each search in the reversed graph from an unassigned start discovers one SCC.

The word reverse is essential. For 0 → 1, DFS from 0 finishes as [1,0]. Searching the reversed graph from 1 first reaches 0 and incorrectly combines the two singleton SCCs. Starting from 0 first correctly isolates it; the subsequent search from 1 skips already assigned 0.

For a larger trace, use 0→1, 1→0, 1→2, 2→3, 3→2, plus isolated vertex 4. Start vertices numerically; inspect 1's neighbors as 0 then 2:

Stage	Result
First DFS from 0 finishes	[3,2,1,0]
DFS from isolated 4 finishes	[3,2,1,0,4]
Second-pass starts	4,0,1,2,3
New components found	{4}, {0,1}, {2,3}

Component finish times put sources of the original component DAG before their reachable successors in reverse finish order. In the reversed graph, the chosen component cannot reach any still-unassigned predecessor. Searches therefore stay within one unassigned SCC. Both passes together take O(V+E) time and space with adjacency lists. The Princeton directed-graph treatment presents the equivalent convention with the two graphs exchanged.

At 200,000 vertices, recursive DFS can exceed Python's recursion limit. For the first pass, an iterative frame must remember (vertex, next-neighbor-index): advance the index before descending and append to finish when the frame has no neighbors left. Merely appending when you first pop a vertex computes discovery order, not finish order. The second pass only needs a stack of vertices, marked when pushed.

Reconstruct: remove 3→2 from the example. The answer becomes four SCCs: {0,1}, {2}, {3}, {4}. One-way reachability is insufficient to combine 2 and 3.

3. Matching: improve an assignment by changing earlier choices

Left IDs and right IDs are separate namespaces: left 0 and right 0 are different vertices. A matching chooses edges with no repeated endpoint. The task asks for maximum cardinality, not minimum cost. Greedily taking any currently available right vertex produces only a maximal matching: you cannot add an edge without moving an existing assignment, but rerouting may still improve it.

Suppose A connects to X and Y, while B connects only to X. Choosing A–X first blocks B. The alternating path B–X–A–Y starts and ends unmatched; it alternates an unused edge, a used edge, then an unused edge. Flip all three: remove A–X and add B–X plus A–Y. The matching grows from one edge to two, and no endpoint is used twice.

Store both directions, pairU[left] and pairV[right], with -1 for unmatched. Update both arrays when a path succeeds. A path with k+1 unused edges and k used edges increases cardinality by exactly one. If no augmenting path exists, the matching is maximum: comparing it with a larger matching would expose an alternating component containing one more edge from that larger matching, hence an augmenting path.

Scale the search with Hopcroft–Karp

Finding one arbitrary augmenting path at a time can repeat a scan for every matched vertex. For this exercise's large bounds, group shortest augmenting paths into phases:

1. Begin BFS at every unmatched left vertex, with distance 0. From left u, an edge to matched right v continues to pairV[v], whose distance is dist[u]+1. A free right ends a path at dist[u]+1; record the smallest such terminal distance, shortest.
2. Search only edges consistent with the BFS layers. Descending through a matched right requires its mate's distance to be exactly one larger. Accept a free right only when dist[u]+1 == shortest. Stop expanding layers at or beyond shortest.
3. Augment along a maximal collection of these shortest paths before rebuilding BFS. Keep a per-left next-edge cursor so failed branches are not scanned repeatedly during the phase; mark an exhausted left vertex unavailable for that phase.
4. Stop when BFS finds no free-right terminal.

Distances here count left-to-right steps, not every edge of the alternating path. In B–X–A–Y, B has distance 0, A has distance 1, and the terminal distance is 2, although the path has three graph edges. Initially, a phase can match A–X. The next BFS finds the rerouting path of terminal distance 2.

The standard phase argument makes the shortest augmenting-path length increase between phases, giving O(sqrt(V)) phases. With adjacency lists and cursors, the total bound is O((V+E) sqrt(V)), including isolated vertices, with O(V+E) space. See the original Hopcroft–Karp paper for the phase proof.

A layered path can still contain many vertices. Use an explicit stack of left vertices plus the chosen right edges, backtrack on exhaustion, and flip the full saved path only on success. The supplied references use this method, so an otherwise valid long path does not depend on a language recursion limit.

Before submitting

For MST, explain why every accepted edge preserves a forest and when the algorithm is complete. For SCCs, write both the append-on-finish list and its reverse before counting components. For matching, draw one case where an earlier assignment must move and identify the shortest terminal layer. Then solve the exercises and use the checkpoint to test the same invariants on different inputs.