using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace IsATree { public class CheckTree { //=============================================================================== //Your Code is Here: public static bool IsTree(string[] vertices, List<KeyValuePair<string, string>> edges) { // string [] color = {"White","Gray","Black"}; Dictionary<string, string> color = new Dictionary<string, string>(); Dictionary<string, List<string>> adj = new Dictionary<string, List<string>>(); for (int i = 0; i < edges.Count; i++) { if (!adj.ContainsKey(edges[i].Key))//to know if the key exists in the dictionary or not. adj[edges[i].Key] = new List<string>(); adj[edges[i].Key].Add(edges[i].Value); } for (int i = 0; i < vertices.Length; i++) { color[vertices[i]] = "White"; // Set every vertex to white. } bool DFS(string ITEM) { color[ITEM] = "Gray"; if (adj.ContainsKey(ITEM)) { List<string> list = adj[ITEM]; for (int i = 0; i < adj[ITEM].Count; i++) { if (color[list[i]] == "White") { if (!DFS(list[i])) return false; } if (color[list[i]] == "Gray") { return false; } } } color[ITEM] = "Black"; // If the node is black, return true because the tree ended. return true; } for (int i = 0; i < vertices.Length; i++) { if (color[vertices[i]] == "White") // check if the color of the Node is white or Not { if (!DFS(vertices[i])) //Go make a DFS and say if the result is a DFS or not. return false; } } return true; } } }

dXNpbmcgU3lzdGVtOyB1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsgdXNpbmcgU3lzdGVtLkxpbnE7IHVzaW5nIFN5c3RlbS5UZXh0OyBuYW1lc3BhY2UgSXNBVHJlZSB7IHB1YmxpYyBjbGFzcyBDaGVja1RyZWUgeyAvLz09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0gLy9Zb3VyIENvZGUgaXMgSGVyZTogcHVibGljIHN0YXRpYyBib29sIElzVHJlZShzdHJpbmdbXSB2ZXJ0aWNlcywgTGlzdDxLZXlWYWx1ZVBhaXI8c3RyaW5nLCBzdHJpbmc+PiBlZGdlcykgeyAvLyBzdHJpbmcgW10gY29sb3IgPSB7IldoaXRlIiwiR3JheSIsIkJsYWNrIn07IERpY3Rpb25hcnk8c3RyaW5nLCBzdHJpbmc+IGNvbG9yID0gbmV3IERpY3Rpb25hcnk8c3RyaW5nLCBzdHJpbmc+KCk7IERpY3Rpb25hcnk8c3RyaW5nLCBMaXN0PHN0cmluZz4+IGFkaiA9IG5ldyBEaWN0aW9uYXJ5PHN0cmluZywgTGlzdDxzdHJpbmc+PigpOyBmb3IgKGludCBpID0gMDsgaSA8IGVkZ2VzLkNvdW50OyBpKyspIHsgaWYgKCFhZGouQ29udGFpbnNLZXkoZWRnZXNbaV0uS2V5KSkvL3RvIGtub3cgaWYgdGhlIGtleSBleGlzdHMgaW4gdGhlIGRpY3Rpb25hcnkgb3Igbm90LiBhZGpbZWRnZXNbaV0uS2V5XSA9IG5ldyBMaXN0PHN0cmluZz4oKTsgYWRqW2VkZ2VzW2ldLktleV0uQWRkKGVkZ2VzW2ldLlZhbHVlKTsgfSBmb3IgKGludCBpID0gMDsgaSA8IHZlcnRpY2VzLkxlbmd0aDsgaSsrKSB7IGNvbG9yW3ZlcnRpY2VzW2ldXSA9ICJXaGl0ZSI7IC8vIFNldCBldmVyeSB2ZXJ0ZXggdG8gd2hpdGUuIH0gYm9vbCBERlMoc3RyaW5nIElURU0pIHsgY29sb3JbSVRFTV0gPSAiR3JheSI7IGlmIChhZGouQ29udGFpbnNLZXkoSVRFTSkpIHsgTGlzdDxzdHJpbmc+IGxpc3QgPSBhZGpbSVRFTV07IGZvciAoaW50IGkgPSAwOyBpIDwgYWRqW0lURU1dLkNvdW50OyBpKyspIHsgaWYgKGNvbG9yW2xpc3RbaV1dID09ICJXaGl0ZSIpIHsgaWYgKCFERlMobGlzdFtpXSkpIHJldHVybiBmYWxzZTsgfSBpZiAoY29sb3JbbGlzdFtpXV0gPT0gIkdyYXkiKSB7IHJldHVybiBmYWxzZTsgfSB9IH0gY29sb3JbSVRFTV0gPSAiQmxhY2siOyAvLyBJZiB0aGUgbm9kZSBpcyBibGFjaywgcmV0dXJuIHRydWUgYmVjYXVzZSB0aGUgdHJlZSBlbmRlZC4gcmV0dXJuIHRydWU7IH0gZm9yIChpbnQgaSA9IDA7IGkgPCB2ZXJ0aWNlcy5MZW5ndGg7IGkrKykgeyBpZiAoY29sb3JbdmVydGljZXNbaV1dID09ICJXaGl0ZSIpIC8vIGNoZWNrIGlmIHRoZSBjb2xvciBvZiB0aGUgTm9kZSBpcyB3aGl0ZSBvciBOb3QgeyBpZiAoIURGUyh2ZXJ0aWNlc1tpXSkpIC8vR28gbWFrZSBhIERGUyBhbmQgc2F5IGlmIHRoZSByZXN1bHQgaXMgYSBERlMgb3Igbm90LiByZXR1cm4gZmFsc2U7IH0gfSByZXR1cm4gdHJ1ZTsgfSB9IH0=