Created
April 24, 2016 00:40
-
-
Save jianminchen/3722227eb8c3df4085c10e34779763bf to your computer and use it in GitHub Desktop.
Even Tree - HackerRank - study C# solution - very readable code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace Solution | |
{ | |
class Solution | |
{ | |
private static Node tree; | |
private static IDictionary<int, Node> nodeMap = new Dictionary<int, Node>(); | |
static void Main(string[] args) | |
{ | |
string[] counts = Console.ReadLine().Split(' '); | |
int M = int.Parse(counts[1]); | |
while(M-- > 0) | |
{ | |
string[] edge = Console.ReadLine().Split(' '); | |
AddEdge(int.Parse(edge[0]), int.Parse(edge[1])); | |
} | |
int result = Traverse(tree); | |
Console.WriteLine(result); | |
} | |
private static int Traverse(Node node) | |
{ | |
int result = 0; | |
foreach (var child in node.Children) | |
{ | |
result += Traverse(child); | |
if (child.ChildCount % 2 != 0) | |
{ | |
result++; | |
} | |
else | |
{ | |
node.ChildCount += child.ChildCount + 1; | |
} | |
} | |
return result; | |
} | |
private static void AddEdge(int v1, int v2) | |
{ | |
if (nodeMap.ContainsKey(v1)) | |
{ | |
DoAddEdge(nodeMap[v1], v2); | |
} | |
else if (nodeMap.ContainsKey(v2)) | |
{ | |
DoAddEdge(nodeMap[v2], v1); | |
} | |
else | |
{ | |
tree = new Node(v1); | |
nodeMap[v1] = tree; | |
DoAddEdge(tree, v2); | |
} | |
} | |
private static void DoAddEdge(Node node, int v2) | |
{ | |
var child = new Node(v2); | |
node.Children.Add(child); | |
nodeMap[v2] = child; | |
} | |
} | |
class Node | |
{ | |
internal Node(int id) | |
{ | |
Id = id; | |
Children = new List<Node>(); | |
ChildCount = 0; | |
} | |
internal int ChildCount { get; set; } | |
internal IList<Node> Children { get; private set; } | |
internal int Id { get; private set; } | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment