CareerCup

by doing a bfs starting at given node we can visit all nodes, each time an new node is discovered (until the termination of bfs), create a new node copying its value, however leaving neightbors field null. create a hashtable mapping address of the old node to newly created node. now its just a matter of translation and returning the address (translated from old) of the new root.

public class Node
{
public int Value { get; set; }
public List<Node> Neighbors { get; set; }

public Node(int value)
{
this.Value = value;
}
}

public static Node CloneGraph(Node srcGraph)
{
if (srcGraph == null)
{
return null;
}

Dictionary<Node, Node> srcToDestNodeMapping = new Dictionary<Node, Node>();

Node destGraph = DfsCreateDestNodes(srcGraph, srcToDestNodeMapping);

foreach (Node srcNode in srcToDestNodeMapping.Keys)
{
foreach (Node neighbor in srcNode.Neighbors)
{
srcToDestNodeMapping[srcNode].Neighbors.Add(srcToDestNodeMapping[neighbor]);
}
}

return destGraph;
}

private static Node DfsCreateDestNodes(Node srcNode, Dictionary<Node, Node> srcToDestNodeMapping)
{
if (srcToDestNodeMapping.ContainsKey(srcNode))
{
return null;
}

Node destNode = new Node(srcNode.Value);
destNode.Neighbors = new List<Node>();

srcToDestNodeMapping.Add(srcNode, destNode);

foreach (Node n in srcNode.Neighbors)
{
DfsCreateDestNodes(n, srcToDestNodeMapping);
}

return destNode;
}

public class Node
    {
        public int Value { get; set; }
        public List<Node> Neighbors { get; set; }

        public Node(int value)
        {
            this.Value = value;
        }
    }

    public static Node CloneGraph(Node srcGraph)
    {
        if (srcGraph == null)
        {
            return null;
        }

        Dictionary<Node, Node> srcToDestNodeMapping = new Dictionary<Node, Node>();

        Node destGraph = DfsCreateDestNodes(srcGraph, srcToDestNodeMapping);

        foreach (Node srcNode in srcToDestNodeMapping.Keys)
        {
            foreach (Node neighbor in srcNode.Neighbors)
            {
                srcToDestNodeMapping[srcNode].Neighbors.Add(srcToDestNodeMapping[neighbor]);
            }
        }

        return destGraph;
    }

    private static Node DfsCreateDestNodes(Node srcNode, Dictionary<Node, Node> srcToDestNodeMapping)
    {
        if (srcToDestNodeMapping.ContainsKey(srcNode))
        {
            return null;
        }

        Node destNode = new Node(srcNode.Value);
        destNode.Neighbors = new List<Node>();

        srcToDestNodeMapping.Add(srcNode, destNode);

        foreach (Node n in srcNode.Neighbors)
        {
            DfsCreateDestNodes(n, srcToDestNodeMapping);
        }

        return destNode;
    }

public void clone(Node root) {

       if(root == null) return null;
       Node r1 = createClone(root);
       for(Node n : root.adjacentNodes()) {
             Node n1 = clone(n);
             r1.addNode(n1);

       }
       return r1;

}

void clone(struct node* root)
{
if(p == NULL)
retutn ;
struct node *p = (struct node *)malloc(sizeof(struct node));
p->left = clone(root->right);
p->right = clone(root->left);
}