Graph General — Reasoning Check

Choose the correct graph model for components, dependencies, ratios, and copying.

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

1. Surrounded Regions uses four-direction connectivity. For the six board rows XXXXXX / XOOXXX / XXOXXX / XXXOOX / XXXXOX / XXXXOX, how many O cells become X?

2. An undirected graph has edges A–B, A–C, B–D, and C–D. A clone reaches D first through B and later through C. What must the second encounter do?

Select one answer.

Reuse the existing clone of D from an original-pointer-to-copy map Skip the C–D edge because D was already visited Allocate another copy of D so each recursive branch owns its nodes Attach C’s clone directly to the original D

3. There are six courses 0..5 with prerequisite edges 0→1, 1→2, 3→4, and 4→3. Course 5 is isolated. Kahn’s algorithm emits four courses before the queue empties. What should FindOrder return?

Select one answer.

Any ordering with 3 and 4 appended at the end An empty result because the 3↔4 cycle prevents a complete ordering The four emitted courses as a partial valid answer Only course 5 because it has no dependencies

4. The consistent equations are p/q=4, q/r=0.5, and r/s=4. What is s/p? Enter an exact decimal.

5. A directed prerequisite graph has edges 0→1, 0→2, and 1→2. Union-find says the endpoints of the last edge are already connected. What does that establish?

Select one answer.

The directed graph has a cycle, so no course ordering exists Courses 1 and 2 must be the same vertex The last directed edge must be reversed It detects an undirected cycle, but the directed graph is still acyclic

6. Number of Islands uses only horizontal and vertical neighbors. How many islands are in rows 10101 / 00100 / 11101?

Auto-advance on pass

Join Discord