C# - iterative, 2 steps - clone, then link neighbors


  • 0
    public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) 
    {
        HashSet<UndirectedGraphNode> processed = new HashSet<UndirectedGraphNode>();
        Dictionary<UndirectedGraphNode, UndirectedGraphNode> map = new Dictionary<UndirectedGraphNode,UndirectedGraphNode>();
        Queue<UndirectedGraphNode> queue = new Queue<UndirectedGraphNode>();
        
        // create clones
        queue.Enqueue(node);
        while (queue.Count > 0)
        {
            UndirectedGraphNode n = queue.Dequeue();
            if (node != null && !processed.Contains(n))
            {
                UndirectedGraphNode clone = new UndirectedGraphNode(n.label);
                map.Add(n, clone);
                processed.Add(n);
                foreach (UndirectedGraphNode neighbor in n.neighbors)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        // link neighbors
        processed.Clear();
        queue.Enqueue(node);
        while (queue.Count > 0)
        {
            UndirectedGraphNode n = queue.Dequeue();
            if (node != null && !processed.Contains(n))
            {
                UndirectedGraphNode clone = map[n];
                processed.Add(n);
                foreach (UndirectedGraphNode neighbor in n.neighbors)
                {
                    clone.neighbors.Add(map[neighbor]);
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        return node != null ? map[node] : null;
    }

Log in to reply
 

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