Clone Graph

mediumFREEGraphsBlind 75

Given an adjacency list representation of an undirected graph, create a deep copy (clone) of the graph.

Input: adj_list is a list with one entry per node: the $k$ -th entry (counting from 1) is the list of node $k$ 's neighbour indices (nodes are 1-indexed). Return the cloned adjacency list in the same format: same neighbours in the same order, and fully independent of the input (modifying the clone must not change the original). An empty graph returns an empty list. The tests print each node's neighbours on one line, space-separated.

Example

Input

2,4
1,3
2,4
1,3

Output

Reasoning

Input: adj_list has one entry per node; the $k$ -th entry (counting from 1) lists the labels of node $k$ 's neighbours. In the sample, nodes 1 and 3 each touch 2 and 4, while nodes 2 and 4 each touch 1 and 3.
The graph: the 4 edges $1\text{–}2$ , $2\text{–}3$ , $3\text{–}4$ , $4\text{–}1$ form a 4-cycle. The graph is undirected, so each edge appears from both ends: $2 \times 4 = 8$ entries.
Deep copy: the clone must describe exactly the same graph (same nodes, same neighbour labels, same order) but be fully independent of the original: adding node 3 to node 1's neighbours in the clone must leave the original's node 1 at $\{2, 4\}$ .
Output: the result prints as 2 4, 1 3, 2 4, 1 3, identical to the input line for line.
Edge case: a graph with no nodes clones to an empty result, which the tests print as EMPTY.

Constraints

1 <= number of nodes <= 100
0 <= neighbors per node <= nodes - 1
No self-loops or repeated edges

Learn this in

GraphsDSA Study Plan

More from Blind 75

Alien Dictionaryhard Combination Summedium Word Search IIhard Merge K Sorted Listshard Remove Nth Node From End of Listmedium

Concept primer

Background Knowledge

The problem of cloning a graph involves creating a deep copy of an undirected graph, given its adjacency list representation. To tackle this problem, it's essential to understand the basics of graph theory, including nodes (also known as vertices) and edges. In an undirected graph, edges do not have a direction and are represented by a simple connection between two nodes. The adjacency list representation is a common way to store graphs in memory, where each node is associated with a list of its neighboring nodes.

In the context of graph cloning, a deep copy means creating a new, independent graph that has the same structure and nodes as the original graph. This requires not only copying the nodes but also the edges that connect them, ensuring that the new graph is a faithful replica of the original. Understanding the difference between shallow copy (copying references) and deep copy (copying the actual objects) is crucial in this problem. A shallow copy would only copy the references to the original nodes, resulting in two graphs that are essentially the same object, whereas a deep copy creates a new, separate graph.

To approach this problem, one should be familiar with graph traversal techniques, such as Depth-First Search (DFS) or Breadth-First Search (BFS). These techniques allow you to visit each node in the graph in a systematic way, which is necessary for creating a copy of the graph. Additionally, understanding how to represent graphs in code, using data structures such as dictionaries or lists, is essential for implementing the solution.

Algorithm/Approach

The general approach to solving this problem involves using a graph traversal technique to visit each node in the original graph and create a corresponding node in the new graph. This can be achieved through either a recursive or iterative approach, using a data structure such as a dictionary to keep track of the nodes that have already been visited and cloned. The algorithm should ensure that each node is cloned only once and that the edges between nodes are correctly replicated in the new graph.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a data structure to store the cloned nodes, such as a dictionary that maps the original node to its clone.
Choose a graph traversal technique (e.g., DFS or BFS) to visit each node in the original graph.
For each node, check if it has already been cloned. If not, create a new node and add it to the dictionary.
Iterate through the neighbors of the current node and clone them if they have not been cloned before.
Create edges between the cloned nodes to replicate the structure of the original graph.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to create a deep copy of the graph, resulting in a shallow copy that references the original nodes.
Not keeping track of the nodes that have already been cloned, leading to duplicate nodes in the new graph.
Incorrectly replicating the edges between nodes, resulting in a graph with a different structure than the original.

Time & Space Complexity

The time complexity of the solution will depend on the chosen graph traversal technique and the number of nodes and edges in the graph. In general, the time complexity can be expected to be $O(n + m)$ , where $n$ is the number of nodes and $m$ is the number of edges. The space complexity will also depend on the size of the graph, as a new graph with the same number of nodes and edges needs to be created. The expected space complexity is $O(n + m)$ , as in the worst case, the new graph will have the same number of nodes and edges as the original graph.

solution.py

Python 3.13

Test results