All problems

Clone Graph

Medium · graph traversal

A network of n machines is numbered 0 to n - 1. It is given as an adjacency list: adj[i] holds the numbers of the machines that machine i has a direct cable to. Every cable works in both directions, so if j is in adj[i] then i is in adj[j]. No machine is cabled to itself and no cable is listed twice. The whole network is connected, so every machine can be reached from machine 0.

Build a deep copy of the network: starting from machine 0, walk along the cables and create a brand new node object for every machine you reach, with its own list of neighbours that point at the new nodes, never at the originals. You define the node class yourself. When the copy is complete, return it as an adjacency list in the same form as the input: entry i is the list of neighbour numbers of the copy of machine i, in the same order as in adj[i].

An empty network (adj is empty) copies to an empty network.

Examples

Example 1

Input: adj = [[1, 2], [0, 2], [0, 1]]

Output: [[1, 2], [0, 2], [0, 1]]

Three machines all cabled to each other. The copy has three new nodes with the same links.

Example 2

Input: adj = [[2], [2], [0, 1, 3], [2]]

Output: [[2], [2], [0, 1, 3], [2]]

Machine 2 is a hub with three neighbours. The order inside each list is kept.

Example 3

Input: adj = [[]]

Output: [[]]

A single machine with no cables copies to a single node with no neighbours.

Constraints