description： 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 / / /_/這道題目因為一點點的小bug，整整花了一個小時來debug。 在進行node復制的時候，誤將代碼里的原有的node錯誤的使用成了自己定義的root
/** * 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) { if (node == null) { return null; } // find all node ArrayList<UndirectedGraphNode> arrayNode = findNode(node); // for (UndirectedGraphNode nodex : arrayNode) { // System.out.PRintln(nodex.label); // } // copy node Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>(); for (UndirectedGraphNode root : arrayNode) { map.put(root, new UndirectedGraphNode(root.label)); } //copy neighbors for (UndirectedGraphNode root : arrayNode) { UndirectedGraphNode roots = map.get(root); for (UndirectedGraphNode n : root.neighbors) { UndirectedGraphNode newNode = map.get(n); roots.neighbors.add(newNode); } } return map.get(node); } private ArrayList<UndirectedGraphNode> findNode(UndirectedGraphNode node) { Queue<UndirectedGraphNode> queue = new LinkedList<>(); Set<UndirectedGraphNode> set = new HashSet<>(); queue.offer(node); set.add(node); while (!queue.isEmpty()) { UndirectedGraphNode root = queue.poll(); for (UndirectedGraphNode roots : root.neighbors) { if (!set.contains(roots)) { queue.offer(roots); set.add(roots); } } } return new ArrayList<UndirectedGraphNode>(set); }}新聞熱點
疑難解答
