DFS, simple, with comments, cool technique to clone -- 101ms


  • 0
    V
    public class Solution {
        public HashSet<UndirectedGraphNode> visited, finished;
        public Dictionary<UndirectedGraphNode, UndirectedGraphNode> h = new Dictionary<UndirectedGraphNode, UndirectedGraphNode>();
        
        public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) {
            if (node == null) { return null; }
            visited = finished = new HashSet<UndirectedGraphNode>();
            
            h.Add(node, new UndirectedGraphNode(node.label));
            dfs(node);
            return h[node]; //new root node
        }
        
        public void dfs(UndirectedGraphNode node) {
            if (visited.Contains(node)) return;
            visited.Add(node);
    
            foreach (var nbr in node.neighbors) {
                if (finished.Contains(nbr)) {
                    h[node].neighbors.Add(h[nbr]);
                    continue;
                }
                if (!h.ContainsKey(nbr)) {
                    h.Add(nbr, new UndirectedGraphNode(nbr.label)); //1.clone the node first.
                }
                dfs(nbr);                          //2.dfs it
                h[node].neighbors.Add(h[nbr]);     //3.update the neighbor list.
                finished.Add(node);                //4.mark it as finished
            }
            return;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.