tuenti12.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tuenti12
{
    class Node : IComparable<Node>
    {  
        public string Name { get; set; }

        public string LinkName { get; set; }

        public int NChild { get; set; }
        public int Height { get; set; }
        public int Level { get; set; }
        public Node Parent { get; set; }
        public List<Node> Children { get; set; }


        public void Update()
        {
            if (Children.Count > 0)
            {
                for (int i = 0; i < Children.Count; i++)
                {
                    Children[i].Level = Level + 1;
                    Children[i].Update();
                    NChild += Children[i].NChild + 1;
                    Height = Math.Max(Height, Children[i].Height + 1); 
                }
            }
        }

        public void ReSort()
        {
            if (Children.Count > 0)
            {
                for (int i = 0; i < Children.Count; i++)
                {
                    Children[i].ReSort();
                }
                Children.Sort();
            }
        }

        private void List(List<Node> lst)
        {
            lst.Add(this);
            if (Children.Count > 0)
            {
                for (int i = 0; i < Children.Count; i++)
                {
                    Children[i].List(lst);
                }
            }
        }

        public string GetPairNames(Node otherNode)
        {
            var l1 = new List<Node>();
            var l2 = new List<Node>();

            List(l1);
            otherNode.List(l2);

            for (int lvl = 0; lvl <= Height; lvl++)
            {
                var nodes1 = l1.Where(n => n.Level == lvl).ToList();
                var nodes2 = l2.Where(n => n.Level == lvl).ToList();

                nodes1.Sort();
                nodes2.Sort();

                for (int i = 0; i < nodes1.Count; i++)
                {
                    nodes1[i].LinkName = nodes2[i].Name;
                }
            }

            l1 = l1.OrderBy(n => n.Name).ToList();
            var result = "";
            for (int i = 0; i < l1.Count; i++)
            {
                result += l1[i].Name + "/" + l1[i].LinkName + " ";
            }

            return result;
        }

        public bool CompareTree(Node other)
        {
            if (Children.Count == other.Children.Count)
            {
                if (Children.Count == 0) return true;
                for (int i = 0; i < Children.Count; i++)
                {
                    if (!Children[i].CompareTree(other.Children[i])) 
                        return false;
                }

                return true;
            }
            return false;
        }
        
        public int CompareTo(Node other)
        {
            var r = Compare(other);
            if (r == 0)
                return Name.CompareTo(other.Name);
            else
                return r;
        }

        public int Compare(Node other)
        {
            if (Children.Count == other.Children.Count) 
            {
                for (int i = 0; i < Children.Count; i++)
                {
                    var r = Children[i].Compare(other.Children[i]);
                    if (r != 0) return r;
                }
                return 0;
            } 
            else return Children.Count - other.Children.Count;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //var lines = File.ReadAllLines("inp2.txt");
            //var lines = File.ReadAllLines("inp.txt");
            //var lines = File.ReadAllLines("inp4.txt");
            //var lines = File.ReadAllLines("testInput.txt");

            var lines = File.ReadAllLines("submitInput.txt");
            var n = Convert.ToInt32(lines[0]);

            var origin = BuildTree(lines, 1, n - 1);

            var viruses = new List<Node>();
            var t = Convert.ToInt32(lines[n]);
            for (int i = 0; i < t; i++)
            {
                var start = n + 1 + i * (n - 1);
                var virus = BuildTree(lines, start, n - 1);
                viruses.Add(virus);
            }

            var result = "";
            for (int i = 1; i <= viruses.Count; i++)
            {
                if (origin.CompareTree(viruses[i - 1]) == true)
                {
                    //File.WriteAllText("debug.txt", origin.ToHierrachy("\t") + "\n ********* \n" + viruses[i - 1].ToHierrachy("\t"));

                    result += "Case #" + i.ToString() + ": " + origin.GetPairNames(viruses[i -1]).Trim() + "\n";
                }
                else
                {
                    result += "Case #" + i.ToString() + ": NO\n";
                }
            }

            File.WriteAllText("submitOutput.txt", result);

        }

        static Node BuildTree(string[] lines, int start, int num)
        {
            List<Node> nodes = new List<Node>();

            for (int i = 0; i < num; i++)
            {
                var l = lines[start + i];
                var from = l.Split(' ')[0];
                var to = l.Split(' ')[1];

                var f = nodes.FirstOrDefault(n => n.Name == from);
                var t = nodes.FirstOrDefault(n => n.Name == to);

                if (f == null)
                {
                    f = new Node { Name = from, Children = new List<Node>() };
                    nodes.Add(f);
                }

                if (t == null)
                {
                    t = new Node { Name = to, Children = new List<Node>() };
                    nodes.Add(t);
                }

                if (!f.Children.Exists(n => n.Name == t.Name))
                {
                    f.Children.Add(t);
                    t.Parent = f;
                }
            }

            var root = nodes.FirstOrDefault(n => n.Parent == null);
            root.Update();
            root.ReSort();

            return root;
        }

    }
}