Advertisement
Guest User

Untitled

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