Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created May 3, 2016 23:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/bf0821320af0e549b486997faf11b358 to your computer and use it in GitHub Desktop.
Save jianminchen/bf0821320af0e549b486997faf11b358 to your computer and use it in GitHub Desktop.
Leetcode 133 - Clone Graph - revise the code to fit into online judge
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace cloneGraph
{
/*
* source code from web blog:
* http://www.programcreek.com/2012/12/leetcode-clone-graph-java/
*
* Leetcode Clone Graph
*
* http://www.cnblogs.com/springfor/p/3874591.html
*
*/
/**
Definition for undirected graph.
*/
// Undirected Graph Node - Node
class UndirectedGraphNode
{
public int label;
public List<UndirectedGraphNode> neighbors;
public UndirectedGraphNode(int x)
{
label = x;
neighbors = new List<UndirectedGraphNode>();
}
}
class Program
{
static void Main(string[] args)
{
// {0, 1, 2#1, 2#2, 2}
UndirectedGraphNode node0 = new UndirectedGraphNode(0);
UndirectedGraphNode node1 = new UndirectedGraphNode(1);
UndirectedGraphNode node2 = new UndirectedGraphNode(2);
List<UndirectedGraphNode> list0 = new List<UndirectedGraphNode>();
list0.Add(node1);
list0.Add(node2);
node0.neighbors = list0;
node1.neighbors = new List<UndirectedGraphNode>();
node1.neighbors.Add(node2);
node2.neighbors = new List<UndirectedGraphNode>();
node2.neighbors.Add(node2);
UndirectedGraphNode newClone = cloneGraph(node0);
UndirectedGraphNode newClone2 = cloneGraph(node1);
UndirectedGraphNode newClone3 = cloneGraph(node2);
}
/*
* Quickly go over the code with test case
*
*/
public static UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;
Queue<UndirectedGraphNode> queue = new Queue<UndirectedGraphNode>();
Dictionary<UndirectedGraphNode, UndirectedGraphNode> map =
new Dictionary<UndirectedGraphNode,UndirectedGraphNode>();
UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);
queue.Enqueue(node);
map.Add(node, newHead);
while(queue.Count > 0 ){
UndirectedGraphNode curr = (UndirectedGraphNode)queue.Dequeue();
IList<UndirectedGraphNode> currNeighbors = curr.neighbors;
foreach (UndirectedGraphNode aNeighbor in currNeighbors){
if(!map.ContainsKey(aNeighbor)){
UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor.label);
map.Add(aNeighbor,copy);
map[curr].neighbors.Add(copy);
queue.Enqueue(aNeighbor);
}else{
map[curr].neighbors.Add(map[aNeighbor]);
}
}
}
return newHead;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment