FilesExpand file tree

 master

/

CloneGraph.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (56 loc) · 2.04 KB

 master

/

CloneGraph.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (56 loc) · 2.04 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

/**

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

*

* <p>OJ's undirected graph serialization: Nodes are labeled uniquely.

*

* <p>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}.

*

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

*

* <p>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:

*

* <p>1 / \ / \ 0 --- 2 / \ \_/

*/

import java.util.HashMap;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.Map;

import java.util.Queue;

import java.util.Set;

public class CloneGraph {

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

if (node == null) return node;

Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();

queue.add(node);

Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();

Map<UndirectedGraphNode, UndirectedGraphNode> map =

new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

while (!queue.isEmpty()) {

UndirectedGraphNode n = queue.remove();

if (visited.contains(n)) continue;

visited.add(n);

UndirectedGraphNode clone;

if (!map.containsKey(n)) {

clone = new UndirectedGraphNode(n.label);

map.put(n, clone);

} else {

clone = map.get(n);

}

for (UndirectedGraphNode child : n.neighbors) {

queue.add(child);

UndirectedGraphNode cloneChild;

if (!map.containsKey(child)) {

cloneChild = new UndirectedGraphNode(child.label);

map.put(child, cloneChild);

} else {

cloneChild = map.get(child);

}

clone.neighbors.add(cloneChild);

}

}

return map.get(node);

}

}