Three graph questions, three invariants

• MST: join every vertex while preserving an acyclic forest.
• SCC: separate mutual reachability from one-way reachability.
• Matching: assign each endpoint at most once, while allowing rerouting.

Predict which problem needs undirected edges, directed edges, or separate left/right IDs.

Kruskal: pause before accepting an edge

Edges: AB:-2, AC:1, BC:1, CD:4, BD:7.

After AB and AC, the total is -1. BC is cheap; should it be accepted?

No. B and C already share a DSU root. Skip BC, select CD, finish with three edges and total 3.

The exchange argument preserves an optimum after each accepted crossing edge. Negative weights are valid.

SCC: one missing reversal changes the result

Original graph: 0 → 1.

• Append on DFS finish: [1,0].
• Reverse graph: 1 → 0.
• Starting from 1 would incorrectly merge the vertices.
• Start in reverse finish order [0,1]: two SCCs.

Reusing discovery order or the first pass's visited set is a different algorithm.

Reconstruct the two passes

Edges: 0↔1, 1→2, 2↔3. Vertex 4 is isolated.

With the lesson's neighbor order:

• Finish list: [3,2,1,0,4].
• Reversed starts: [4,0,1,2,3].
• New components: {4}, {0,1}, {2,3}.

Iterative first-pass frames retain the next neighbor index so vertices append on exit.

A maximal assignment can still be improved

A connects to X and Y; B connects only to X.

Current matching: A–X. Follow B–X–A–Y.

Remove A–X, add B–X and A–Y. Size increases from 1 to 2.

Update both left and right mate tables. No right vertex gets two owners.

Hopcroft–Karp: shortest paths in phases

BFS begins at every free left vertex.

For B–X–A–Y: dist[B]=0, dist[A]=1, terminal distance 2.

DFS follows increasing layers and accepts a free right only at the shortest terminal distance. Collect a maximal set of shortest paths, then rebuild BFS.

A per-left edge cursor avoids rescanning exhausted branches during the phase.

Depth is a resource too

An alternating path may be thousands of vertices long even with few edges per vertex.

Use a stack of left vertices and selected right edges. Backtrack on failure; flip the saved path on success.

MST: O(E log E) sorting. SCC: O(V+E). Matching: O((V+E) sqrt(V)).

Explain before implementing

• What certifies an MST is complete?
• When exactly does a first-pass SCC frame append its vertex?
• Why does a matching path increase cardinality by one?
• What shortest-layer condition prevents arbitrary-depth augmentations in a phase?

Now test your answers on the three exercises and checkpoint.