Advertisement
VSZM

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;
  6. using System.Threading.Tasks;
  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>();
  18.             nodes.Add(start_node.number, start_node);
  19.             nodes.Add(finish_node.number, finish_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));
  29.             Console.ReadLine();
  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();
  42.                 topological_order.Add(current);
  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.  
  55.             return topological_order;
  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)
  67.                     criticalNodes.Add(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))
  84.                     nodes.Add(from_node, new Node(from_node));
  85.                 if (!nodes.ContainsKey(to_node))
  86.                     nodes.Add(to_node, new Node(to_node));
  87.  
  88.                 nodes[from_node].directlyAccessibleNodes.Add(nodes[to_node]);
  89.                 nodes[to_node].nodesDirectlyAccessingThisNode.Add(nodes[from_node]);
  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. }
Advertisement
RAW Paste Data Copied
Advertisement