C#•2y ago

LeetCode - Clone Graph [Answered]

Hey, trying to solve - https://leetcode.com/problems/clone-graph/ basically - question is to deep-clone a graph. Could anyone helped me figure out why my solution isn't valid? Error message - You must return a copy of all the nodes in the original graph My code -

  public Node CloneGraph(Node node)
    {
        var map = new Dictionary<int, Node>();
        var clone = new Node(node.val);
        dfs(node, clone, map);
        return clone;
    }
    
    public void dfs(Node source, Node target, Dictionary<int, Node> map)
    {
        foreach(var sourceNeighbor in source.neighbors)
        {
            Node targetNeighbor;
            if(!map.TryGetValue(sourceNeighbor.val, out targetNeighbor))
            {
                targetNeighbor = new Node(sourceNeighbor.val);
                map.Add(targetNeighbor.val, targetNeighbor);                                
                dfs(sourceNeighbor, targetNeighbor, map);  
            }
            target.neighbors.Add(targetNeighbor);
        }
    }

  public Node CloneGraph(Node node)
    {
        var map = new Dictionary<int, Node>();
        var clone = new Node(node.val);
        dfs(node, clone, map);
        return clone;
    }
    
    public void dfs(Node source, Node target, Dictionary<int, Node> map)
    {
        foreach(var sourceNeighbor in source.neighbors)
        {
            Node targetNeighbor;
            if(!map.TryGetValue(sourceNeighbor.val, out targetNeighbor))
            {
                targetNeighbor = new Node(sourceNeighbor.val);
                map.Add(targetNeighbor.val, targetNeighbor);                                
                dfs(sourceNeighbor, targetNeighbor, map);  
            }
            target.neighbors.Add(targetNeighbor);
        }
    }

3 Replies

Pobiega•2y ago

have you made unittests? so you can test it with a few known graphs

Ben•2y ago

fml... found the issue. I needed to add the initial clone variable to the hashmap before going into the dfs logic. I'll close this, thanks Pobiega

Accord•2y ago

✅ This post has been marked as answered!

Gaming

Programming

LeetCode - Clone Graph [Answered]