C#_HAmilton_&_20

class Program
    {
        public class Stack
        {
            private class Node //вложенный класс, реализующий элемент стека
            {
                private object inf;
                private Node next;
                public Node(object nodeInfo)
                {
                    inf = nodeInfo;
                    next = null;
                }
                public Node Next
                {
                    get { return next; }
                    set { next = value; }
                }
                public object Inf
                {
                    get { return inf; }
                    set { inf = value; }
                }
            } //конец класса Node
            private Node head; //ссылка на вершину стека
            public Stack() //конструктор класса, создает пустой стек
            {
                head = null;
            }
            public void Push(object nodeInfo) // добавляет элемент в вершину стека
            {
                Node r = new Node(nodeInfo);
                r.Next = head;
                head = r;
            }
            public object Pop() //извлекает элемент из вершины стека, если он не пуст
            {
                if (head == null)
                {
                    throw new Exception("Стек пуст");
                }
                else
                {
                    Node r = head;
                    head = r.Next;
                    return r.Inf;
                }
            }
            public bool IsEmpty //определяет пуст или нет стек
            {
                get
                {
                    if (head == null)
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }
        public class Queue
        {
            private class Node //вложенный класс, реализующий базовый элемент очереди
            {
                private object inf;
                private Node next;
                public Node(object nodeInfo)
                {
                    inf = nodeInfo;
                    next = null;
                }
                public Node Next
                {
                    get { return next; }
                    set { next = value; }
                }
                public object Inf
                {
                    get { return inf; }
                    set { inf = value; }
                }
            } //конец класса Node
            private Node head;
            private Node tail;
            public Queue()
            {
                head = null;
                tail = null;
            }
            public void Add(object nodeInfo)
            {
                Node r = new Node(nodeInfo);
                if (head == null)
                {
                    head = r;
                    tail = r;
                }
                else
                {
                    tail.Next = r;
                    tail = r;
                }
            }
            public object Take()
            {
                if (head == null)
                {
                    throw new Exception("Очередь пуста.");
                }
                else
                {
                    Node r = head;
                    head = head.Next;
                    if (head == null)
                    {
                        tail = null;
                    }
                    return r.Inf;
                }
            }
            public bool IsEmpty
            {
                get
                {
                    if (head == null)
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }

        public class Graph
        {
            private class Node //вложенный класс для скрытия данных и алгоритмов
            {
                private int[,] array; //матрица смежности
                public int this[int i, int j] //индексатор для обращения к матрице смежности
                {
                    get
                    {
                        return array[i, j];
                    }
                    set
                    {
                        array[i, j] = value;
                    }
                }
                public bool this[int i] //индексатор для обращения к матрице меток
                {
                    get
                    {
                        return nov[i];
                    }
                    set
                    {
                        nov[i] = value;
                    }
                }
                public int Size //свойство для получения размерности матрицы смежности
                {
                    get
                    {
                        return array.GetLength(0);
                    }
                }
                private bool[] nov; //вспомогательный массив: если i-ый элемент массива равен
                                    //true, то i-ая вершина еще не просмотрена; если i-ый
                                    //элемент равен false, то i-ая вершина просмотрена
                public void NovSet() //метод помечает все вершины графа как непросмотреные
                {
                    for (int i = 0; i < Size; i++)
                    {
                        nov[i] = true;
                    }
                }
                //конструктор вложенного класса, инициализирует матрицу смежности и
                // вспомогательный массив
                public Node(int[,] a)
                {
                    array = a;
                    nov = new bool[a.GetLength(0)];
                }
                //реализация алгоритма обхода графа в глубину
                public void Dfs(int v)
                {
                    Console.Write("{0} ", v); //просматриваем текущую вершину
                    nov[v] = false; //помечаем ее как просмотренную
                                    // в матрице смежности просматриваем строку с номером v
                    for (int u = 0; u < Size; u++)
                    {
                        //если вершины v и u смежные, к тому же вершина u не просмотрена,
                        if (array[v, u] != 0 && nov[u])
                        {
                            Dfs(u); // то рекурсивно просматриваем вершину
                        }
                    }
                }
                //реализация алгоритма обхода графа в ширину
                public void Bfs(int v)
                {
                    Queue q = new Queue(); // инициализируем очередь
                    q.Add(v); //помещаем вершину v в очередь
                    nov[v] = false; // помечаем вершину v как просмотренную
                    while (!q.IsEmpty) // пока очередь не пуста
                    {
                        v = Convert.ToInt32(q.Take()); //извлекаем вершину из очереди
                        Console.Write("{0} ", v); //просматриваем ее
                        for (int u = 0; u < Size; u++) //находим все вершины
                        {
                            if (array[v, u] != 0 && nov[u]) // смежные с данной и еще не просмотренные
                            {
                                q.Add(u); //помещаем их в очередь
                                nov[u] = false; //и помечаем как просмотренные
                            }
                        }
                    }
                }
                public long[,] Floyd(out int[,] p)
                {
                    int i, j, k;
                    //создаем массивы р и а
                    long[,] a = new long[Size, Size];
                    p = new int[Size, Size];
                    for (i = 0; i < Size; i++)
                    {
                        for (j = 0; j < Size; j++)
                        {
                            if (i == j)
                            {
                                a[i, j] = 0;
                            }
                            else
                            {
                                if (array[i, j] == 0)
                                {
                                    a[i, j] = int.MaxValue;
                                }
                                else
                                {
                                    a[i, j] = array[i, j];
                                }
                            }
                            p[i, j] = -1;
                        }
                    }
                    //осуществляем поиск кратчайших путей
                    for (k = 0; k < Size; k++)
                    {
                        for (i = 0; i < Size; i++)
                        {
                            for (j = 0; j < Size; j++)
                            {
                                long distance = a[i, k] + a[k, j];
                                if (a[i, j] > distance)
                                {
                                    a[i, j] = distance;
                                    p[i, j] = k;
                                }
                            }
                        }
                    }
                    return a;//в качестве результата возвращаем массив кратчайших путей между
                } //всеми парами вершин


                public void SearchG(int v, ref int[,] a, ref Stack c) //во вложенном классе
                {
                    for (int i = 0; i < a.GetLength(0); i++)
                    {
                        if (a[v, i] != 0)
                        {
                            a[v, i] = 0; a[i, v] = 0;
                            SearchG(i, ref a, ref c);
                        }
                    }
                    c.Push(v);
                }

                public long[] Dijkstr(int v, out int[] p)
                {
                    nov[v] = false; // помечаем вершину v как просмотренную
                                    //создаем матрицу с
                    int[,] c = new int[Size, Size];
                    for (int i = 0; i < Size; i++)
                    {
                        for (int u = 0; u < Size; u++)
                        {
                            if (array[i, u] == 0 || i == u)
                            {
                                c[i, u] = int.MaxValue;
                            }
                            else
                            {
                                c[i, u] = array[i, u];
                            }
                        }
                    }
                    //создаем матрицы d и p
                    long[] d = new long[Size];
                    p = new int[Size];
                    for (int u = 0; u < Size; u++)
                    {
                        if (u != v)
                        {
                            d[u] = c[v, u];
                            p[u] = v;
                        }
                    }
                    for (int i = 0; i < Size - 1; i++) // на каждом шаге цикла
                    {
                        // выбираем из множества V\S такую вершину w, что D[w] минимально
                        long min = int.MaxValue;
                        int w = 0;
                        for (int u = 0; u < Size; u++)
                        {
                            if (nov[u] && min > d[u])
                            {
                                min = d[u];
                                w = u;
                            }
                        }
                        nov[w] = false; //помещаем w в множество S
                                        //для каждой вершины из множества V\S определяем кратчайший путь от
                                        // источника до этой вершины
                        for (int u = 0; u < Size; u++)
                        {
                            long distance = d[w] + c[w, u];
                            if (nov[u] && d[u] > distance)
                            {
                                d[u] = distance;
                                p[u] = w;
                            }
                        }
                    }
                    return d; //в качестве результата возвращаем массив кратчайших путей для
                } //заданного источника

                  //восстановление пути от вершины a до вершины b для алгоритма Дейкстры
                public void WayDijkstr(int a, int b, int[] p, ref Stack items)
                {
                    items.Push(b); //помещаем вершину b в стек
                    if (a == p[b]) //если предыдущей для вершины b является вершина а, то
                    {
                        items.Push(a); //помещаем а в стек и завершаем восстановление пути
                    }
                    else //иначе метод рекурсивно вызывает сам себя для поиска пути
                    { //от вершины а до вершины, предшествующей вершине b
                        WayDijkstr(a, p[b], p, ref items);
                    }
                }
                public void SearchGm(int k, ref int[] St,int start)//вложенный класс
                {
                    int v = St[k-1];
                    for (int j = 0; j < array.GetLength(0); j++)
                    {
                        if (array[v, j] != 0)
                        {
                            if (k == array.GetLength(0) && j==start)
                            {
                                St[k] = j;
                                foreach (int item in St)
                                {
                                   Console.Write(item+" ");
                                }
                                Console.WriteLine();
                            }
                            else
                            {
                                if (nov[j])
                                {
                                    if (k >= St.Length)
                                        return;
                                    St[k] = j;
                                    nov[j] = false;
                                    SearchGm(k + 1, ref St,start);
                                    nov[j] = true;

                                }
                            }

                        }

                    }

                }

            } //конец вложенного клаcса
            private Node graph; //закрытое поле, реализующее АТД «граф»

            public Graph(string name) //конструктор внешнего класса
            {
                using (StreamReader file = new StreamReader(name))
                {
                    int n = int.Parse(file.ReadLine());
                    int[,] a = new int[n, n];
                    for (int i = 0; i < n; i++)
                    {
                        string line = file.ReadLine();
                        string[] mas = line.Split(' ');
                        for (int j = 0; j < n; j++)
                        {
                            a[i, j] = int.Parse(mas[j]);
                        }
                    }
                    graph = new Node(a);
                }
            }
            public bool GraphCheck()
            {
                bool check = true;
                int count = 0;
                int temp = 0;
                for (int i = 0; i < graph.Size; i++)
                {
                    for (int j = 0; j < graph.Size; j++)
                    {
                        if (graph[i, j] != 0)
                            count++;
                    }
                    if (count % 2 != 0)
                    {
                        temp++;
                    }
                    count = 0;
                }
                if (temp % 2 != 0)
                    check = false;
                return check;
            }
            //метод выводит матрицу смежности на консольное окно
            public void Show()
            {
                for (int i = 0; i < graph.Size; i++)
                {
                    for (int j = 0; j < graph.Size; j++)
                    {
                        Console.Write("{0,4}", graph[i, j]);
                    }
                    Console.WriteLine();
                }
            }
            public void Dfs(int v)
            {
                graph.NovSet();//помечаем все вершины графа как непросмотренные
                graph.Dfs(v); //запускаем алгоритм обхода графа в глубину
                Console.WriteLine();
            }
            public void Bfs(int v)
            {
                graph.NovSet();//помечаем все вершины графа как непросмотренные
                graph.Bfs(v); //запускаем алгоритм обхода графа в ширину
                Console.WriteLine();
            }


            public void Neighbouring()
            {
                Console.Write("Вершины не смежные с вершиной: ");
                int v = int.Parse(Console.ReadLine());
                //просматриваем строку с номером v в матрице смежности
                for (int i = 0; i < graph.Size; i++)
                {
                    //если на пересечении строки v и столбца i стоит не ноль, то вершина i является
                    //соседней для вершины v
                    if (graph[v, i] == 0 && v != i)
                    {
                        Console.Write("{0} ", i);
                    }
                }
                Console.WriteLine();
            }
            public void SearchG(int start) //во внешнем классе Эйлеров
            {
                int[,] a = new int[graph.Size, graph.Size];
                for (int i = 0; i < graph.Size; i++)
                {
                    for (int j = 0; j < graph.Size; j++)
                    {
                        a[i, j] = graph[i, j];
                    }
                }
                Stack c = new Stack();
                graph.SearchG(start, ref a, ref c);
                //while (c.Count != 0)
                while (!c.IsEmpty)
                {
                    Console.Write("{0} ", (int)c.Pop() );
                }
            }
            public void SearchGm()//внешний класс Гамильтонов
            {
                graph.NovSet();
                int[] St = new int[graph.Size + 1];
                graph[0] = false; //обращение к индексатору
                Console.Write("Вершина:");
                int k = int.Parse(Console.ReadLine());
                int start = k;
                St[0] = k;
               // St[0] = 0;
                graph.SearchGm(k, ref St,start);
            }

            public int GetLength()
            {
                return graph.Size;
            }

              //восстановление пути от вершины a до вершины в для алгоритма Флойда
            public void WayFloyd(int a, int b, int[,] p, ref Queue items)
            {
                int k = p[a, b];
                //если k<> -1, то путь состоит более чем из двух вершин а и b, и проходит через
                //вершину k, поэтому
                if (k != -1)
                {
                    // рекурсивно восстанавливаем путь между вершинами а и k
                    WayFloyd(a, k, p, ref items);
                    items.Add(k); //помещаем вершину к в очередь
                                  // рекурсивно восстанавливаем путь между вершинами k и b
                    WayFloyd(k, b, p, ref items);
                }
            }

            public int CentralApex()
            {
            int[,] p;
            long[,] a = graph.Floyd(out p); //вызываем алгоритм Флойда
            long min = int.MaxValue;
            int imin = -1;

            for (int i = 0; i < graph.Size; i++)
            {
                int imax = i;
                int jmax = 0;
                // для каждой строки матрицы определяем эксцентриситет
                for (int j = 0; j < graph.Size; j++)
                {
                    if (a[i, j] > a[imax, jmax])
                    {
                        imax = i;
                        jmax = j;
                    }
                }
                //среди найденных эксцентриситетов определяем наименьший
                if (a[imax, jmax] < min)
                {
                    min = a[imax, jmax];
                    imin = imax;
                }
            }
            return imin; //возвращаем номер вершины с наименьшим эксцентриситетом
        }
            public void Dijkstr(int v)
            {
                graph.NovSet();//помечаем все вершины графа как непросмотренные
                int[] p;
                long[] d = graph.Dijkstr(v, out p); //запускаем алгоритм Дейкстры
                                                    //анализируем полученные данные и выводим их на экран
                Console.WriteLine("Длина кратчайшие пути от вершины {0} до вершины", v);
                for (int i = 0; i < graph.Size; i++)
                {
                    if (i != v)
                    {
                        Console.Write("{0} равна {1}, ", i, d[i]);
                        Console.Write("путь ");
                        if (d[i] != int.MaxValue)
                        {
                            Stack items = new Stack();
                            graph.WayDijkstr(v, i, p, ref items);
                            while (!items.IsEmpty)
                            {
                                Console.Write("{0} ", items.Pop());
                            }
                        }
                    }
                    Console.WriteLine();
                }
            }

            public void InMinDistance()
            {
                graph.NovSet(); //помечаем все вершины графа как непросмотренные
                int[] p;
                Console.Write("Введите вершину=");
                int v = int.Parse(Console.ReadLine());
                long[] d = graph.Dijkstr(v, out p); //запускаем алгоритм дейкстры
                long min = long.MaxValue;
                //вычисляем наименьшее расстояние для достижимых вершин
                for (int i = 0; i < p.Length; i++)
                    if (min > d[i] && d[i] != 0)
                        min = d[i];
                //выводим на экран все вершины, находящиеся от заданной на наименьшем расстоянии
                if (min == 0)
                    Console.WriteLine("Из заданной вершины другие вершины недостижимы");
                else
                {
                    Console.Write("На наименьшем удалении от вершины {0} находятся вершины: ",v);
                    for (int i = 0; i < d.Length; i++)
                        if (d[i] == min)
                            Console.Write(i+" ");
                    Console.WriteLine();
                }

            }

        }



        static void Main(string[] args)
        {
            Graph g = new Graph(@"E:/input.txt");
            g.SearchGm();
            //g.InMinDistance();
        }
    }