Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace _04.RecoverMessage
- {
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- internal class Node : IComparable
- {
- public Node()
- {
- this.Children = new HashSet<Node>();
- }
- public char Value { get; set; }
- public bool HasParent { get; set; }
- public double Weight { get; set; }
- public ICollection<Node> Children { get; set; }
- public int CompareTo(object obj)
- {
- return this.Value.CompareTo((obj as Node).Value);
- }
- public override int GetHashCode()
- {
- return this.Value.GetHashCode();
- }
- public override bool Equals(object obj)
- {
- return this.Value.Equals((obj as Node).Value);
- }
- }
- internal class Program
- {
- internal static void Main()
- {
- var n = int.Parse(Console.ReadLine());
- string[] messages = new string[n];
- var graph = BuildGraph(messages);
- var recoveredMessage = RecoverMessage(graph);
- Console.WriteLine(recoveredMessage);
- }
- private static string RecoverMessage(List<Node> graph)
- {
- var recoveredMessage = new StringBuilder();
- while (graph.Count > 0)
- {
- var root = graph.Where(node => node.HasParent == false).OrderBy(node => node.Value).First();
- recoveredMessage.Append(root.Value);
- graph.Remove(root);
- foreach (var child in root.Children)
- {
- if (!graph.Any(node => node.Children.Any(c => c == child)))
- {
- child.HasParent = false;
- }
- }
- }
- return recoveredMessage.ToString();
- }
- private static List<Node> BuildGraph(string[] messages)
- {
- var letters = new HashSet<Node>();
- for (int i = 0; i < messages.Length; i++)
- {
- messages[i] = Console.ReadLine();
- for (int j = 0; j < messages[i].Length; j++)
- {
- letters.Add(new Node() { Value = messages[i][j] });
- }
- }
- var graph = letters.ToList();
- for (int i = 0; i < messages.Length; i++)
- {
- for (int j = 0; j < messages[i].Length; j++)
- {
- var index = Array.IndexOf(graph.Select(g => g.Value).ToArray(), messages[i][j]);
- if (j < messages[i].Length - 1)
- {
- var childNode = new Node() { Value = messages[i][j + 1] };
- var childIndex = Array.IndexOf(graph.ToArray(), childNode);
- graph[childIndex].HasParent = true;
- graph[index].Children.Add(graph[childIndex]);
- }
- }
- }
- return graph;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement