Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace Sticks
- {
- using System;
- using System.Collections.Generic;
- class Program
- {
- static void Main(string[] args)
- {
- int stickCount = int.Parse(Console.ReadLine());
- int stickPlacings = int.Parse(Console.ReadLine());
- Dictionary<int,List<int>> graph = new Dictionary<int, List<int>>();
- for (int i = 0; i < stickCount; i++)
- {
- graph[i] = new List<int>();
- }
- int[] predecessorsCount = new int[graph.Count];
- for (int i = 0; i < stickPlacings; i++)
- {
- var sticks = Console.ReadLine().Split(' ');
- var topStick = int.Parse(sticks[0]);
- var bottomStick = int.Parse(sticks[1]);
- graph[topStick].Add(bottomStick);
- }
- for (int stick = 0; stick < graph.Count; stick++)
- {
- foreach (int bottomStick in graph[stick])
- {
- predecessorsCount[bottomStick]++;
- }
- }
- var isRemoved = new bool[graph.Count];
- var liftedSticks = new LinkedList<int>();
- var stickRemoved = true;
- while (stickRemoved)
- {
- stickRemoved = false;
- for (int stick = graph.Count - 1; stick >= 0; stick--)
- {
- if (predecessorsCount[stick] == 0 && !isRemoved[stick])
- {
- foreach (int bottomStick in graph[stick])
- {
- predecessorsCount[bottomStick]--;
- }
- isRemoved[stick] = true;
- stickRemoved = true;
- liftedSticks.AddLast(stick);
- break;
- }
- }
- }
- if (liftedSticks.Count < graph.Count)
- {
- Console.WriteLine("Cannot lift all sticks");
- }
- Console.WriteLine(string.Join(" ",liftedSticks));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement