Advertisement
VSZM

Kritikus szakaszok

Feb 2nd, 2017
191
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.     /**
  11.         A feladatunk valójában az, hogy az összes lehetséges módon bejárjuk a gráfot a startcsúcstól a célcsúcsig és
  12.         lejegyezzük az összes lehetséges utat. Az utakban előforduló csúcsok halmazainak úniója adja a végeredményt.
  13.         Magyarul a végeredményt azon csúcsok adják, amelyek minden lehetséges útban szerepelnek.    
  14.         Ehhez elég jó megoldás lesz, ha minden csúcsra megnézzük, hogy ha kivesszük az adott csúcsot,
  15.         akkor is elérhető-e a start node-ból a cél node.
  16.  
  17.          *
  18.          *  */
  19.  
  20.     public class _70
  21.     {
  22.         public void Solve()
  23.         {
  24.             List<string> lines = new List<string>(File.ReadAllLines("../../70_input_1.txt"));
  25.             Node start_node = new Node(int.Parse(lines[0].Split()[2]));
  26.             Node finish_node = new Node(int.Parse(lines[0].Split()[3]));
  27.             Dictionary<int, Node> nodes = new Dictionary<int, Node>();
  28.             nodes.Add(start_node.number, start_node);
  29.             nodes.Add(finish_node.number, finish_node);
  30.  
  31.             lines.RemoveAt(0);
  32.             PreProcess(lines, nodes);
  33.             List<Node> critical_nodes = GetCriticalNodes(start_node, finish_node, nodes);
  34.  
  35.             //foreach (var road in all_different_roads)
  36.             //{
  37.             //    Console.WriteLine(string.Join(" ", road));
  38.             //}
  39.  
  40.             Console.WriteLine(critical_nodes.Count);
  41.             Console.WriteLine(string.Join(" ", critical_nodes));
  42.             Console.ReadLine();
  43.         }
  44.  
  45.         private List<Node> GetCriticalNodes(Node start_node, Node finish_node, Dictionary<int, Node> nodes)
  46.         {
  47.             List<Node> critical_nodes = new List<Node>();
  48.  
  49.             foreach (var node in nodes.Values)
  50.             {
  51.                 var nodes_without_the_current_node = new Dictionary<int, Node>(nodes);
  52.                 nodes_without_the_current_node.Remove(node.number);
  53.  
  54.                 if (!Dfs(start_node, finish_node, nodes_without_the_current_node))
  55.                 {
  56.                     critical_nodes.Add(node);
  57.                 }
  58.  
  59.             }
  60.  
  61.             critical_nodes.Remove(finish_node);
  62.  
  63.             return critical_nodes;
  64.         }
  65.  
  66.         private bool Dfs(Node start_node, Node goal_node, Dictionary<int, Node> nodes)
  67.         {
  68.             Stack<List<Node>> expandable_roads = new Stack<List<Node>>();
  69.             expandable_roads.Push(new List<Node>() { start_node });
  70.  
  71.             while(expandable_roads.Count > 0)
  72.             {
  73.                 var current_road = expandable_roads.Pop();
  74.                 var current_node = current_road.Last();
  75.  
  76.                 if (goal_node == current_node)
  77.                 {
  78.                     return true;
  79.                 }
  80.  
  81.                 foreach (var child in current_node.directlyAccessibleNodes.Where(node => nodes.Values.Contains(node)))
  82.                 {
  83.                     var new_road = new List<Node>(current_road);
  84.                     if (!new_road.Contains(child))// avoiding cycles
  85.                     {
  86.                         new_road.Add(child);
  87.                         expandable_roads.Push(new_road);
  88.                     }
  89.                 }
  90.             }
  91.  
  92.             return false;
  93.         }
  94.  
  95.         private void PreProcess(List<string> lines, Dictionary<int, Node> nodes)
  96.         {
  97.             lines.ForEach(line =>
  98.             {
  99.                 int from_node = int.Parse(line.Split()[0]);
  100.                 int to_node = int.Parse(line.Split()[1]);
  101.  
  102.                 if (!nodes.ContainsKey(from_node))
  103.                     nodes.Add(from_node, new Node(from_node));
  104.                 if (!nodes.ContainsKey(to_node))
  105.                     nodes.Add(to_node, new Node(to_node));
  106.  
  107.                 nodes[from_node].directlyAccessibleNodes.Add(nodes[to_node]);
  108.             });
  109.         }
  110.  
  111.  
  112.         private class Node
  113.         {
  114.             public int number;
  115.             public HashSet<Node> directlyAccessibleNodes = new HashSet<Node>();
  116.  
  117.             public Node(int _number)
  118.             {
  119.                 number = _number;
  120.             }
  121.  
  122.             public override int GetHashCode()
  123.             {
  124.                 return number.GetHashCode();
  125.             }
  126.  
  127.             public override bool Equals(object obj)
  128.             {
  129.                 if (obj is Node)
  130.                 {
  131.                     return number == ((Node)obj).number;
  132.                 }
  133.  
  134.                 return false;
  135.             }
  136.  
  137.             public override string ToString()
  138.             {
  139.                 return number.ToString();
  140.             }
  141.         }
  142.  
  143.     }
  144. }
Advertisement
RAW Paste Data Copied
Advertisement