Clone Graph
Medium
Hash Table
Depth-First Search
Breadth-First Search
Graph
Given a reference of a node in a connected undirected graph, return *a deep copy (clone) of the graph*. Each node in the graph contains a value (`int`) and a list (`List[Node]`) of its neighbors. The graph is represented in the test cases using an adjacency list. Each node has an index starting from 1, and `adjList[i]` is a list of node indices that are adjacent to node `i + 1`.
Example 1
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Example 2
Input: adjList = [[]]
Output: [[]]
Example 3
Input: adjList = []
Output: []

Constraints

  • •The number of nodes in the graph is in the range [0, 100].
  • •1 <= Node.val <= 100
  • •Node.val is unique for each node.
  • •There are no repeated edges and no self-loops in the graph.
  • •The Graph is connected and all nodes can be visited starting from the given node.
Time Complexity
O(V+E)
Space Complexity
O(V)
14
Case 1
Input: [[2,4],[1,3],[2,4],[1,3]]
Expected: [[2,4],[1,3],[2,4],[1,3]]
Case 2
Input: [[]]
Expected: [[]]
Case 3
Input: []
Expected: []