Kritikus szakaszok enhanced

Feb 4th, 2017
197
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Text;
5. using System.IO;
7.
8. namespace Nevezetes_Algoritmusok
9. {
10.     public class _70
11.     {
12.         public void Solve()
13.         {
14.             List<string> lines = new List<string>(File.ReadAllLines("../../70_input_1.txt"));
15.             Node start_node = new Node(int.Parse(lines[0].Split()[2]));
16.             Node finish_node = new Node(int.Parse(lines[0].Split()[3]));
17.             Dictionary<int, Node> nodes = new Dictionary<int, Node>();
20.
21.             lines.RemoveAt(0);
22.             PreProcess(lines, nodes);
23.             List<Node> topological_order = Topoligical_Sort(start_node, nodes);
24.             //Console.WriteLine(string.Join(" ", topological_order));
25.             List<Node> critical_nodes = GetCriticalNodes(start_node, finish_node, topological_order);
26.
27.             Console.WriteLine(critical_nodes.Count);
28.             Console.WriteLine(string.Join(" ", critical_nodes));
30.         }
31.
32.         //Kahn's algorithm
33.         private List<Node> Topoligical_Sort(Node start_node, Dictionary<int, Node> nodes)
34.         {
35.             List<Node> topological_order = new List<Node>();
36.             Stack<Node> zero_in_count_nodes = new Stack<Node>();
37.             zero_in_count_nodes.Push(start_node);
38.
39.             while (zero_in_count_nodes.Count > 0)
40.             {
41.                 Node current = zero_in_count_nodes.Pop();
43.                 HashSet<Node> children = new HashSet<Node>(current.directlyAccessibleNodes);
44.
45.                 foreach (Node child in children)
46.                 {
47.                     child.nodesDirectlyAccessingThisNode.Remove(current);
48.                     current.directlyAccessibleNodes.Remove(child);
49.
50.                     if (child.nodesDirectlyAccessingThisNode.Count == 0)
51.                         zero_in_count_nodes.Push(child);
52.                 }
53.             }
54.
56.         }
57.
58.         private List<Node> GetCriticalNodes(Node start_node, Node finish_node, List<Node> topological_order)
59.         {
60.             List<Node> criticalNodes = new List<Node>();
61.             int magic = 0;
62.
63.             foreach (var node in topological_order)
64.             {
65.                 magic -= node.InCount;
66.                 if (magic == 0 && node != start_node && node != finish_node)
68.
69.                 magic += node.OutCount;
70.             }
71.
72.
73.             return criticalNodes;
74.         }
75.
76.         private void PreProcess(List<string> lines, Dictionary<int, Node> nodes)
77.         {
78.             lines.ForEach(line =>
79.             {
80.                 int from_node = int.Parse(line.Split()[0]);
81.                 int to_node = int.Parse(line.Split()[1]);
82.
83.                 if (!nodes.ContainsKey(from_node))
85.                 if (!nodes.ContainsKey(to_node))
87.
90.                 nodes[from_node].OutCount++;
91.                 nodes[to_node].InCount++;
92.             });
93.         }
94.
95.
96.         private class Node
97.         {
98.             public int number;
99.             public HashSet<Node> nodesDirectlyAccessingThisNode = new HashSet<Node>();
100.             public HashSet<Node> directlyAccessibleNodes = new HashSet<Node>();
101.
102.             public int InCount;
103.             public int OutCount;
104.
105.             public Node(int _number)
106.             {
107.                 number = _number;
108.             }
109.
110.             public override int GetHashCode()
111.             {
112.                 return number.GetHashCode();
113.             }
114.
115.             public override bool Equals(object obj)
116.             {
117.                 if (obj is Node)
118.                 {
119.                     return number == ((Node)obj).number;
120.                 }
121.
122.                 return false;
123.             }
124.
125.             public override string ToString()
126.             {
127.                 return number.ToString();
128.             }
129.         }
130.
131.     }
132. }