Advertisement
Guest User

Untitled

a guest
Aug 29th, 2016
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.13 KB | None | 0 0
  1.  
  2. namespace Sticks
  3. {
  4.     using System;
  5.     using System.Collections.Generic;
  6.  
  7.     class Program
  8.     {
  9.         static void Main(string[] args)
  10.         {
  11.             int stickCount = int.Parse(Console.ReadLine());
  12.             int stickPlacings = int.Parse(Console.ReadLine());
  13.  
  14.            Dictionary<int,List<int>> graph = new Dictionary<int, List<int>>();
  15.             for (int i = 0; i < stickCount; i++)
  16.             {
  17.                 graph[i] = new List<int>();
  18.             }
  19.             int[] predecessorsCount = new int[graph.Count];
  20.             for (int i = 0; i < stickPlacings; i++)
  21.             {
  22.                 var sticks = Console.ReadLine().Split(' ');
  23.                 var topStick = int.Parse(sticks[0]);
  24.                 var bottomStick = int.Parse(sticks[1]);
  25.                 graph[topStick].Add(bottomStick);
  26.             }
  27.             for (int stick = 0; stick < graph.Count; stick++)
  28.             {
  29.                 foreach (int bottomStick in graph[stick])
  30.                 {
  31.                     predecessorsCount[bottomStick]++;
  32.                 }
  33.             }
  34.             var isRemoved = new bool[graph.Count];
  35.             var liftedSticks = new LinkedList<int>();
  36.             var stickRemoved = true;
  37.             while (stickRemoved)
  38.             {
  39.                 stickRemoved = false;
  40.                 for (int stick = graph.Count - 1; stick >= 0; stick--)
  41.                 {
  42.                     if (predecessorsCount[stick] == 0 && !isRemoved[stick])
  43.                     {
  44.                         foreach (int bottomStick in graph[stick])
  45.                         {
  46.                             predecessorsCount[bottomStick]--;
  47.                         }
  48.                         isRemoved[stick] = true;
  49.                         stickRemoved = true;
  50.                         liftedSticks.AddLast(stick);
  51.                         break;
  52.                     }
  53.                 }
  54.             }
  55.             if (liftedSticks.Count < graph.Count)
  56.             {
  57.                 Console.WriteLine("Cannot lift all sticks");
  58.             }
  59.  
  60.             Console.WriteLine(string.Join(" ",liftedSticks));
  61.         }
  62.     }
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement