Graph General

Reader guide and study workflow · Complete course map

Decide what a connection lets you conclude

Draw edges A→B, A→C, B→D, C→D. If arrows are prerequisites, these tasks can all finish: A, then B and C in either order, then D. If the same drawing is treated as undirected connections, it contains a cycle. So “find a cycle” is not a sufficient model of the task. State what an edge means before choosing traversal or a connectivity structure.

For an undirected map, a slow baseline answers each new connection query by exploring all reachable vertices again. If edges are only being added, we can retain a summary: which component each vertex belongs to. Joining two different components changes that partition; joining vertices already connected closes a cycle. This derives union-find's purpose and also its limitation: a component label cannot tell us which direction prerequisites point.

For prerequisites, instead count obligations that remain unsatisfied. In A→C and B→C, removing A leaves one obligation on C; a boolean “seen from a completed task” would lose that information. Only residual indegree zero makes C ready. Start with all ready tasks, including isolated ones. If tasks remain when the ready set is empty, repeatedly following a remaining predecessor must eventually revisit a task: that proves a directed cycle exists in the remainder.

Let the required output choose the visited state

To count islands, exploring one component marks all its members so the outer scan counts it once. To preserve regions with an escape route, starting from every interior cell repeats the same work. Start at the known escape boundary instead and mark everything reachable from it. The neighbor rule remains four-directional in both problems; diagonal visual contact supplies no edge.

To clone a graph, a visited boolean tells us too little. When an edge reaches an already-seen original, which copied object should receive that edge? Store original pointer→clone pointer. Insert the clone before exploring its neighbors so a cycle can point back to it. Pointer keys also support an extension with repeated payloads; this exercise itself promises unique values. Parallel neighbor entries must remain parallel in the copy.

For ratio equations, a path carries a product, not a shortest distance. Consistency ensures alternative known paths agree up to rounding; without it, “return any found path” would need a conflict policy. The same queue or recursion syntax can support these tasks, but the carried meaning is different in each one.

Prerequisites and readiness

Know adjacency lists, four-direction grid neighbors, maps keyed by pointers, and stack/queue traversal. Be able to distinguish a directed prerequisite from an undirected connection, and an edge weight from a distance to minimize.

Reasoning workshop: choose what an edge means

Three drawings, three different questions

In islands, a vertex is a land cell and an edge is orthogonal adjacency. In course scheduling, a vertex is a course and edge b->a means a cannot begin until b finishes. In division queries, an edge a->b stores the multiplicative ratio a/b. Reusing BFS syntax does not make these questions equivalent: the first counts components, the second orders dependencies, and the third carries a product along any consistent path.

Flood fill is a proof about an entire component

For land rows 110 / 010 / 001, starting at (0,0) claims three cells. The bottom-right cell is a second component; diagonal contact is irrelevant. Increment the component count at the first unvisited representative, not once per stack pop. Mark before pushing so a cell reached from two neighbors is scheduled only once.

Surrounded Regions reverses the question: mark the O cells that can escape. The board XXXX / XOOX / XXOX / XOXX has an isolated border O at (3,1) that survives, while the three connected interior O cells are captured. Adding an O corridor between those groups would protect all of them. A local count of neighboring X cells cannot establish enclosure.

Memoization can preserve identity, not just save time

For a triangle A-B-C-A, allocate clone A and record originalA->cloneA before descending. The recursive revisit from C then closes an edge to the same clone A. Memoizing only after descendants finish recurses forever. Copying values without checking pointer disjointness can hide a shallow copy; tests must inspect topology and ensure the original graph is untouched.

Dependency removal gives a schedulability certificate

For 0->1, 0->2, 1->3, 2->3, indegrees begin [0,1,1,2]. Removing 0 makes 1 and 2 available. Removing only 1 leaves course 3 with one unmet dependency. Only after removing 2 does 3 become available. Both [0,1,2,3] and [0,2,1,3] are valid outputs. If a disconnected cycle remains, an apparently good prefix is not a complete solution.

The stopping argument matters: in a finite residual graph where every vertex has an incoming residual edge, following predecessors must eventually revisit a vertex. That is the cycle preventing progress. This is stronger than saying “the queue became empty, so something failed.”

Connectivity summaries do not encode direction

For edges [1,2], [2,3], [1,3], union-find accepts the first two and rejects the third because its endpoints already share a component. Equality of immediate parent entries is not enough; find must reach the representatives. This detects the closing edge of an undirected tree-plus-one-edge input. It is not a substitute for directed cycle detection in course prerequisites.

For ratio equations a/b=2 and b/c=3, products yield a/c=6 and c/a=1/6. BFS is used only to find a path; it is not minimizing the product. This interpretation requires mutually consistent finite nonzero equations and representable reciprocal/path products. Unknown x/x remains -1 because x is not part of the known graph.

Reconstruction lab and answer key

Number of Islands

For rows 101 / 010 / 101, count components under the published neighbor rule. Then change to eight-direction neighbors: what answer changes, and which part of the algorithm must change?

Model answer

With four-direction edges, all five land cells are separate islands. With diagonals allowed, the center connects all four corners, giving one island. The outer component-counting logic is unchanged; the neighbor generator, and therefore the meaning of reachability, changes. A visually nearby cell is not an edge unless the contract permits it.

Surrounded Regions

On rows XXXX / XOOX / XXOX / XXOX, which O cells survive? If the bottom-row O is changed to X, what changes and why?

Model answer

All four O cells survive initially: (3,2) is on the border and reaches (2,2), (1,2), and (1,1). Closing that single exit makes the remaining three O cells enclosed, so all flip to X. The decision depends on a complete escape path, not the number of adjacent X cells.

Clone Graph

Now relax this exercise’s unique-value promise: original A and B may share the same value. A.Neighbors=[B,B,A] and B.Neighbors=[A]. What must the clone preserve, and why would a value-keyed map cease to be sufficient?

Model answer

Allocate distinct A′ and B′, separate from both originals. A′.Neighbors must be [B′,B′,A′] in that order, preserving the duplicate edge and self-loop; B′.Neighbors=[A′]. A boolean visited set cannot supply the already-created target object, and a value-keyed map would collapse A and B.

Evaluate Division

Given p/q=0.5 and q/r=4, derive p/r and r/p. Then suppose a third equation p/r=3 is added: which stated assumption fails, and why can a path search no longer promise a unique answer?

Model answer

The products give p/r=2 and r/p=0.5. Adding p/r=3 contradicts the derived ratio and breaks mutual consistency. Different paths would return different products. The current API assumes consistent input; handling contradictory measurements would require a policy such as rejecting the system or reporting inconsistency.

Course Schedule

Courses 0 through 4 have prerequisite edges 0→1, 1→0, and 2→3; course 4 is isolated. What can Kahn’s algorithm process, and why is that insufficient to return true?

Model answer

Initially 2 and 4 are ready; processing 2 also makes 3 ready. Those three can finish in an order consistent with 2 before 3. The 0↔1 component never obtains indegree zero, so only three of five courses finish. A valid order for one component does not establish feasibility of the whole graph.

Course Schedule II

For four courses with only edge 0→2, a proposed result is [0,1,1,2]. All listed prerequisites appear in order. Is that enough? Specify a validator that accepts every legitimate ordering.

Model answer

No: course 1 is duplicated and course 3 is missing. Require length four, every label in [0,4), each exactly once, and position(0)<position(2). More generally check every prerequisite edge. Avoid comparing with one preferred sequence because independent courses may appear in many valid orders.

Redundant Connection

Process [1,2], [2,3], [3,4], [1,4]. What does the last edge add to reachability, and why is it the requested edge even though removing any edge on the cycle would restore a tree?

Model answer

After the first three edges, 1 and 4 already belong to one connected component. The last edge changes no reachability and closes the cycle, so return [1,4] in its input orientation. Under the tree-plus-one-edge promise, this is the last input edge on the cycle, matching the required tie rule.

Problems in this module

• Number of Islands
• Surrounded Regions
• Clone Graph
• Evaluate Division
• Course Schedule
• Course Schedule II
• Redundant Connection

Interactive checkpoint

Open the Graph General quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable