71. Clone Graph

Medium · Graph

You are given a graph represented as an adjacency list, where nodes are numbered 1 to n. Your task is to create a deep clone of this graph and return it in the same adjacency list format.

Input: An array where input[i] contains the list of neighbour node values for node (i+1). For example, input[0] = [2,4] means node 1 is connected to nodes 2 and 4.

Output: Return a new adjacency list representing the cloned graph. The clone must be structurally identical to the input — preserve the order of neighbours and any duplicate values in the neighbour lists. Your cloned graph should be completely independent from the original (no shared node objects).

Examples

Example 1
Input: [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 4-node cycle; clone has the same adjacency list
Example 2
Input: []
Output: []
Explanation: Empty graph

Constraints