Kritikus szakaszok

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;

namespace Nevezetes_Algoritmusok
{
    /**
        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
        lejegyezzük az összes lehetséges utat. Az utakban előforduló csúcsok halmazainak úniója adja a végeredményt.
        Magyarul a végeredményt azon csúcsok adják, amelyek minden lehetséges útban szerepelnek.
        Ehhez elég jó megoldás lesz, ha minden csúcsra megnézzük, hogy ha kivesszük az adott csúcsot,
        akkor is elérhető-e a start node-ból a cél node.

         *
         *  */

    public class _70
    {
        public void Solve()
        {
            List<string> lines = new List<string>(File.ReadAllLines("../../70_input_1.txt"));
            Node start_node = new Node(int.Parse(lines[0].Split()[2]));
            Node finish_node = new Node(int.Parse(lines[0].Split()[3]));
            Dictionary<int, Node> nodes = new Dictionary<int, Node>();
            nodes.Add(start_node.number, start_node);
            nodes.Add(finish_node.number, finish_node);

            lines.RemoveAt(0);
            PreProcess(lines, nodes);
            List<Node> critical_nodes = GetCriticalNodes(start_node, finish_node, nodes);

            //foreach (var road in all_different_roads)
            //{
            //    Console.WriteLine(string.Join(" ", road));
            //}

            Console.WriteLine(critical_nodes.Count);
            Console.WriteLine(string.Join(" ", critical_nodes));
            Console.ReadLine();
        }

        private List<Node> GetCriticalNodes(Node start_node, Node finish_node, Dictionary<int, Node> nodes)
        {
            List<Node> critical_nodes = new List<Node>();

            foreach (var node in nodes.Values)
            {
                var nodes_without_the_current_node = new Dictionary<int, Node>(nodes);
                nodes_without_the_current_node.Remove(node.number);

                if (!Dfs(start_node, finish_node, nodes_without_the_current_node))
                {
                    critical_nodes.Add(node);
                }

            }

            critical_nodes.Remove(finish_node);

            return critical_nodes;
        }

        private bool Dfs(Node start_node, Node goal_node, Dictionary<int, Node> nodes)
        {
            Stack<List<Node>> expandable_roads = new Stack<List<Node>>();
            expandable_roads.Push(new List<Node>() { start_node });

            while(expandable_roads.Count > 0)
            {
                var current_road = expandable_roads.Pop();
                var current_node = current_road.Last();

                if (goal_node == current_node)
                {
                    return true;
                }

                foreach (var child in current_node.directlyAccessibleNodes.Where(node => nodes.Values.Contains(node)))
                {
                    var new_road = new List<Node>(current_road);
                    if (!new_road.Contains(child))// avoiding cycles
                    {
                        new_road.Add(child);
                        expandable_roads.Push(new_road);
                    }
                }
            }

            return false;
        }

        private void PreProcess(List<string> lines, Dictionary<int, Node> nodes)
        {
            lines.ForEach(line =>
            {
                int from_node = int.Parse(line.Split()[0]);
                int to_node = int.Parse(line.Split()[1]);

                if (!nodes.ContainsKey(from_node))
                    nodes.Add(from_node, new Node(from_node));
                if (!nodes.ContainsKey(to_node))
                    nodes.Add(to_node, new Node(to_node));

                nodes[from_node].directlyAccessibleNodes.Add(nodes[to_node]);
            });
        }


        private class Node
        {
            public int number;
            public HashSet<Node> directlyAccessibleNodes = new HashSet<Node>();

            public Node(int _number)
            {
                number = _number;
            }

            public override int GetHashCode()
            {
                return number.GetHashCode();
            }

            public override bool Equals(object obj)
            {
                if (obj is Node)
                {
                    return number == ((Node)obj).number;
                }

                return false;
            }

            public override string ToString()
            {
                return number.ToString();
            }
        }

    }
}