FilesExpand file tree

 master

/

CloneGraph.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

69 lines (56 loc) · 2.26 KB

 master

/

CloneGraph.java

Copy path

Top

File metadata and controls

• Code
• Blame

69 lines (56 loc) · 2.26 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

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

/*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 undirected graph.

* class UndirectedGraphNode {

* int label;

* ArrayList<UndirectedGraphNode> neighbors;

* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

* };

*/

public class Solution {

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

if (node == null) {

return null;

}

ArrayList<UndirectedGraphNode> nodes = new ArrayList<UndirectedGraphNode>();

HashMap<UndirectedGraphNode, UndirectedGraphNode> map

= new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

// clone nodes

nodes.add(node);

map.put(node, new UndirectedGraphNode(node.label));

int start = 0;

while (start < nodes.size()) {

UndirectedGraphNode head = nodes.get(start++);

for (int i = 0; i < head.neighbors.size(); i++) {

UndirectedGraphNode neighbor = head.neighbors.get(i);

if (!map.containsKey(neighbor)) {

map.put(neighbor, new UndirectedGraphNode(neighbor.label));

nodes.add(neighbor);

}

}

}

// clone neighbors

for (int i = 0; i < nodes.size(); i++) {

UndirectedGraphNode newNode = map.get(nodes.get(i));

for (int j = 0; j < nodes.get(i).neighbors.size(); j++) {

newNode.neighbors.add(map.get(nodes.get(i).neighbors.get(j)));

}

}

return map.get(node);

}

}