FilesExpand file tree

 master

/

clone-graph.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (48 loc) · 1.64 KB

 master

/

clone-graph.py

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (48 loc) · 1.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

# Time: O(n)

# Space: O(n)

#

# Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

#

#

# OJ's undirected graph serialization:

# Nodes are labeled uniquely.

#

# We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

# As an example, consider the serialized graph {0,1,2#1,2#2,2}.

#

# The graph has a total of three nodes, and therefore contains three parts as separated by #.

#

# First node is labeled as 0. Connect node 0 to both nodes 1 and 2.

# Second node is labeled as 1. Connect node 1 to node 2.

# Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

# Visually, the graph looks like the following:

#

# 1

# / \

# / \

# 0 --- 2

# / \

# \_/

#

# Definition for a undirected graph node

class UndirectedGraphNode:

def __init__(self, x):

self.label = x

self.neighbors = []

class Solution:

# @param node, a undirected graph node

# @return a undirected graph node

def cloneGraph(self, node):

if node is None:

return None

cloned_node = UndirectedGraphNode(node.label)

cloned, queue = {node:cloned_node}, [node]

while queue:

current = queue.pop()

for neighbor in current.neighbors:

if neighbor not in cloned:

queue.append(neighbor)

cloned_neighbor = UndirectedGraphNode(neighbor.label)

cloned[neighbor] = cloned_neighbor

cloned[current].neighbors.append(cloned[neighbor])

return cloned[node]