Advertisement
anilak

Untitled

Sep 13th, 2014
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.08 KB | None | 0 0
  1. namespace _04.RecoverMessage
  2. {
  3.     using System;
  4.     using System.Collections.Generic;
  5.     using System.Linq;
  6.     using System.Text;
  7.  
  8. internal class Node : IComparable
  9.     {
  10.         public Node()
  11.         {
  12.             this.Children = new HashSet<Node>();
  13.         }
  14.  
  15.         public char Value { get; set; }
  16.  
  17.         public bool HasParent { get; set; }
  18.  
  19.         public double Weight { get; set; }
  20.  
  21.         public ICollection<Node> Children { get; set; }
  22.  
  23.         public int CompareTo(object obj)
  24.         {
  25.             return this.Value.CompareTo((obj as Node).Value);
  26.         }
  27.  
  28.         public override int GetHashCode()
  29.         {
  30.             return this.Value.GetHashCode();
  31.         }
  32.  
  33.         public override bool Equals(object obj)
  34.         {
  35.             return this.Value.Equals((obj as Node).Value);
  36.         }
  37.     }
  38.  
  39.     internal class Program
  40.     {
  41.         internal static void Main()
  42.         {
  43.             var n = int.Parse(Console.ReadLine());
  44.             string[] messages = new string[n];
  45.             var graph = BuildGraph(messages);
  46.             var recoveredMessage = RecoverMessage(graph);
  47.             Console.WriteLine(recoveredMessage);
  48.         }
  49.  
  50.         private static string RecoverMessage(List<Node> graph)
  51.         {
  52.             var recoveredMessage = new StringBuilder();
  53.  
  54.             while (graph.Count > 0)
  55.             {
  56.                 var root = graph.Where(node => node.HasParent == false).OrderBy(node => node.Value).First();
  57.                 recoveredMessage.Append(root.Value);
  58.                 graph.Remove(root);
  59.  
  60.                 foreach (var child in root.Children)
  61.                 {
  62.                     if (!graph.Any(node => node.Children.Any(c => c == child)))
  63.                     {
  64.                         child.HasParent = false;
  65.                     }
  66.                 }
  67.             }
  68.  
  69.             return recoveredMessage.ToString();
  70.         }
  71.  
  72.         private static List<Node> BuildGraph(string[] messages)
  73.         {
  74.             var letters = new HashSet<Node>();
  75.             for (int i = 0; i < messages.Length; i++)
  76.             {
  77.                 messages[i] = Console.ReadLine();
  78.                 for (int j = 0; j < messages[i].Length; j++)
  79.                 {
  80.                     letters.Add(new Node() { Value = messages[i][j] });
  81.                 }
  82.             }
  83.  
  84.             var graph = letters.ToList();
  85.             for (int i = 0; i < messages.Length; i++)
  86.             {
  87.                 for (int j = 0; j < messages[i].Length; j++)
  88.                 {
  89.                     var index = Array.IndexOf(graph.Select(g => g.Value).ToArray(), messages[i][j]);
  90.                     if (j < messages[i].Length - 1)
  91.                     {
  92.                         var childNode = new Node() { Value = messages[i][j + 1] };
  93.                         var childIndex = Array.IndexOf(graph.ToArray(), childNode);
  94.                         graph[childIndex].HasParent = true;
  95.                         graph[index].Children.Add(graph[childIndex]);
  96.                     }
  97.                 }
  98.             }
  99.  
  100.             return graph;
  101.         }
  102.     }
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement