/
githubmirror
/
interviews
Обзор
Документация
Войти
/
githubmirror
/
interviews
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
company/google/CloneGraph.java
52 строки
2 KB
Kevin Naughton Jr
finish renaming files and directories
27 мар 2018, 19:52
27 мар 2018, 19:52
ec6dfb5
Код
Авторство
О чём код?
// 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; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class CloneGraph { public HashMap<Integer, UndirectedGraphNode> map = new HashMap<Integer, UndirectedGraphNode>(); public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node == null) { return null; } if(map.containsKey(node.label)) { return map.get(node.label); } UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); map.put(newNode.label, newNode); for(UndirectedGraphNode neighbor : node.neighbors) { newNode.neighbors.add(cloneGraph(neighbor)); } return newNode; } }