Clone Graph
Clone Graph is a medium Graphs problem from the Blind 75. The key pattern is graph traversal with a map, and a good solution runs in O(V + E) time.
Problem
Clone an undirected graph given as a one-indexed adjacency list and print the clone's normalized adjacency list.
Examples
Example 1
Input
[[2,3],[1,3],[1,2]]Output
[[2,3],[1,3],[1,2]]Example 2
Input
[[2,3],[1,3],[1,2,4],[3]]Output
[[2,3],[1,3],[1,2,4],[3]]Example 3
Input
[]Output
[]Approach
Traverse the graph and map every original node to its copy, creating copies on first sight and wiring neighbours through the map.
| Pattern | Graph traversal with a map |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Watch out for
The map is what stops cycles from looping forever.