Graphs
Graphs that are not grids
An adjacency map, and traversing a structure where the nodes are objects rather than coordinates.
Key idea
Edge list to adjacency map
Problems usually hand you a list of edges, which is the wrong shape for traversal because finding a node's neighbors means scanning the whole list. Convert once, up front, into a map from node to its neighbors.
For an undirected graph add both directions. Forgetting one is a bug that makes half the graph unreachable and is invisible on symmetric test cases.
Gotcha
Nodes with no edges never appear
Building the map from edges alone means a node with no edges is absent entirely. If the problem counts isolated nodes, and connectivity problems usually do, iterate over the full node range rather than over the map's keys.
This is the most common off-by-one in graph problems and it produces answers that are exactly right except on inputs containing a lonely node.
Why it works
The traversal is unchanged
With an adjacency map, the traversal is the flood fill from the last lesson with the neighbor loop replaced by a lookup. The visited set holds node identifiers rather than coordinates and nothing else changes.
That is worth internalizing: grid traversal and graph traversal are not two techniques. The grid version computes its neighbors arithmetically and the general version looks them up.
Key idea
Traversing while building a copy
Copying a graph is the Unit 7 old-to-new mapping again, with one difference: a graph has no natural order to walk in, so the copying happens during a traversal rather than in two clean passes.
The map does double duty. It records which originals have been copied, so it is the visited set, and it supplies the copy to link to when an already-seen node is reached again. One dict, two jobs.
Below is the state after one node has been copied and before anything has been linked, which is the moment that makes both jobs work.
Why it works
Record the copy before recursing
The map entry is written before the neighbors are visited. That ordering is what makes cycles terminate: when the recursion comes back around to the starting node, it finds the entry and returns instead of copying again.
Recording afterward would recurse forever on any cycle. This is the same before-or-after ordering question as the running values in Unit 1, with a much harsher failure mode.
Tip
Verify it is really a copy
Two things need checking and only one of them is obvious. The copy must be a different object from the original, which the demonstration above confirms. The harder one is that the copy's neighbors must be copies too, rather than pointing back at the originals.
A partially shared structure is the usual wrong answer here, and it passes any test that only compares values. Assert on identity, not on contents.
Predict the output: the map is also the visited set
A graph whose two nodes point at each other is copied. The map from original to copy is written before any recursion happens. Type the two lines it prints.
Clone Graph
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.