Graphs Beyond Traversal Checkpoint

Justify Kruskal decisions, reconstruct SCC finish order, and trace shortest augmenting paths.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. A connected graph has edges AB:-3, AC:2, BC:4, CD:5, BD:9. What MST total does Kruskal return? Enter one integer.

2. Kruskal has selected n-2 edges in a connected n-vertex graph. The next edge joins vertices with the same DSU root. What should happen?

Select one answer.

Accept it to reach n-1 edges Stop because the graph must be connected already Accept it only if its weight is negative Skip it and continue looking for an edge between components

3. DFS on 0→1→2, starting at 0, appends vertices on finish as [2,1,0]. How many SCCs exist? Enter one integer.

4. A first pass on the original graph appends vertices after all descendants finish. Which second pass implements the lesson’s Kosaraju convention?

Select one answer.

Clear visited, reverse edges, and use the reverse of the appended list Keep visited and traverse reversed edges in appended order Clear visited and use discovery order on the original graph Reverse edges and start from the lowest-degree vertex each time

5. A graph with six vertices contains SCCs {0,1}, {2,3}, {4}, {5}, with an edge from 1 to 2. Why must that one-way edge not combine the first two SCCs?

Select one answer.

An SCC cannot have more than two vertices Every SCC must have the same size There is no return path from {2,3} to {0,1} A vertex can only belong to an SCC if it has a self-loop

6. The matching is A–X and B–Y. A also connects to Z, B also connects to X, and free C connects only to Y. Which rerouting matches all three left vertices?

Select one answer.

Keep A–X, B–Y and also add C–Y Flip C–Y–B–X–A–Z to get C–Y, B–X, A–Z Remove B–Y and stop Move C to Z despite having no C–Z edge

7. BFS finds a shortest free-right terminal distance of 2 in a matching phase. DFS at left u has dist[u]=2 and sees a free right. What is the correct decision?

Select one answer.

Accept it because the right vertex is free Reset all mate tables Treat dist[u] as zero Reject that terminal in this phase because dist[u]+1 is 3

8. A sparse matching instance contains an alternating path with 5,000 left vertices. What implementation change addresses Python recursion depth while preserving the path search?

Select one answer.

Use a stack with edge cursors and flip the saved path on success Limit all augmenting paths to 100 edges Discard already matched edges from the graph permanently Assume sparse graphs have shallow searches

Auto-advance on pass

Join Discord