Clone Graph
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 node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
1 / \ / \ 0 --- 2 / \ \_/
Naive Way:难点在于穿件了新的节点如何找回原来对应的节点,并且输入只有一个节点。
用Map可以正中下怀的解决这个问题。
算法复杂度是O(n),space是O(n)。
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); if(node==null){return null;} // BFS, give every node a clone, put relationship into a map UndirectedGraphNode newHead = new UndirectedGraphNode(node.label); map.put(node,newHead); queue.add(node); while(!queue.isEmpty()){ UndirectedGraphNode temp = queue.poll(); for(int i = 0;i < temp.neighbors.size();i++){ if(!map.containsKey(temp.neighbors.get(i))){ queue.add(temp.neighbors.get(i)); UndirectedGraphNode newNode = new UndirectedGraphNode(temp.neighbors.get(i).label); map.put(temp.neighbors.get(i),newNode); } } } // according to the map, construct new graph queue.add(node); set.add(node); while(!queue.isEmpty()){ UndirectedGraphNode temp = queue.poll(); if(!map.containsKey(temp)){return null;} UndirectedGraphNode clone = map.get(temp); for(int i = 0;i < temp.neighbors.size();i++){ if(!map.containsKey(temp.neighbors.get(i))){return null;} clone.neighbors.add(map.get(temp.neighbors.get(i))); if(!set.contains(temp.neighbors.get(i))){ set.add(temp.neighbors.get(i)); queue.add(temp.neighbors.get(i)); } } } return map.containsKey(node)?map.get(node):null; } }
No comments:
Post a Comment