Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created May 5, 2016 18:44
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/35f3efda39c30d1e993a16a89d14308d to your computer and use it in GitHub Desktop.
Save jianminchen/35f3efda39c30d1e993a16a89d14308d to your computer and use it in GitHub Desktop.
Leetcode 133 Clone Graph - Make the code more flat, remove if/ else statement in the previous version
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 Node
{
public int label;
public List<Node> neighbors;
public Node(int x)
{
label = x;
neighbors = new List<Node>();
}
}
class Program
{
static void Main(string[] args)
{
// {0, 1, 2#1, 2#2, 2}
Node node0 = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
List<Node> list0 = new List<Node>();
list0.Add(node1);
list0.Add(node2);
node0.neighbors = list0;
node1.neighbors = new List<Node>();
node1.neighbors.Add(node2);
node2.neighbors = new List<Node>();
node2.neighbors.Add(node2);
Node newClone = cloneGraph(node0);
// Node newClone2 = cloneGraph(node1);
// Node newClone3 = cloneGraph(node2);
}
/*
* Quickly go over the code with test case
*
*/
public static Node cloneGraph(Node node)
{
if (node == null)
return null;
Queue<Node> queue = new Queue<Node>();
Dictionary<Node, Node> map =
new Dictionary<Node, Node>();
Node newHead = new Node(node.label);
queue.Enqueue(node);
map.Add(node, newHead);
while (queue.Count > 0)
{
Node curr = (Node)queue.Dequeue();
List<Node> currNeighbors = curr.neighbors;
foreach (Node aNeighbor in currNeighbors)
{
bool containing = map.ContainsKey(aNeighbor);
// 1.update queue
if (!containing)
queue.Enqueue(aNeighbor);
// 2. update map
if (!containing)
{
Node copy = new Node(aNeighbor.label);
map.Add(aNeighbor, copy);
}
// 3. update neighbors for cloned graph
// definitely, map.ContainsKey[aNeighbor]
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