Clone Graph

Question

Given a undirected graph in which all nodes are connected.

Return a cloned or deep copied graph.

Each node in the graph contains a value and a neighbor list.

Node Structure

class Node:
  def __init__(self, val=None):
    self.val = val
    self.neighbors = []

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

Constraints

0 <= len(nodes) <= 100

1 <= Node.val <= 100

Node.val is unique..

No self-loops.

The Graph is connected all.

TC

O(v+e), where v is the number of vertices and e is the number of edges.

SC

O(v), where v is the number of vertices.

Solution

▭

graph/Clone Graph.py

from gen.util.ds_network import Network, Node


def solution(node, visited):
    if node.val in visited:
        return visited[node.val]

    copy = Node(node.val)
    visited[node.val] = copy

    #print(node.val)

    for adj_node in node.neighbors:
        copy.neighbors.append(solution(adj_node, visited))
        #print(copy.val, adj_node.val)

    return copy



net = Network()
n1 = net.add_node(1)
n2 = net.add_node(2)
n3 = net.add_node(3)
n4 = net.add_node(4)

n1.set_neighbor(n2, n4)
n2.set_neighbor(n1, n3)
n3.set_neighbor(n2, n4)
n4.set_neighbor(n1, n3)

net.print()

result = solution(n1, {})

#print(result)

Step	node.val
1	1
2	2
3	3
4	4

Step	copy.val	adj_node.val
1	2	1
2	3	2
3	4	1
4	4	3
5	3	4
6	2	3
7	1	2
8	1	4

▯

graph/Clone Graph.py

from gen.util.ds_network import Network, Node


def solution(node, visited):
    if node.val in visited:
        return visited[node.val]

    copy = Node(node.val)
    visited[node.val] = copy

    #print(node.val)

    for adj_node in node.neighbors:
        copy.neighbors.append(solution(adj_node, visited))
        #print(copy.val, adj_node.val)

    return copy



net = Network()
n1 = net.add_node(1)
n2 = net.add_node(2)
n3 = net.add_node(3)
n4 = net.add_node(4)

n1.set_neighbor(n2, n4)
n2.set_neighbor(n1, n3)
n3.set_neighbor(n2, n4)
n4.set_neighbor(n1, n3)

net.print()

result = solution(n1, {})

#print(result)

Step	node.val
1	1
2	2
3	3
4	4

Step	copy.val	adj_node.val
1	2	1
2	3	2
3	4	1
4	4	3
5	3	4
6	2	3
7	1	2
8	1	4