Eyler/Hamilton

using System;
using System.Collections;
using System.IO;

public class Graph
{

    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;
                }
            }
        }
    }

    private class Node //вложенный класс для скрытия данных и алгоритмов
    {
        private int[,] array; //матрица смежности
        public int this[int i, int j] //индексатор для обращения к матрице смежности
        {
            get
            {
                return array[i, j];
            }
            set
            {
                array[i, j] = 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 bool NovGet(int i) //метод помечает все вершины графа как непросмотреные
        {

            return nov[i];

        }
        //конструктор вложенного класса, инициализирует матрицу смежности и
        // вспомогательный массив
        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 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;//в качестве результата возвращаем массив кратчайших путей между
        } //всеми парами вершин

        //восстановление пути от вершины 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 void Reach(int v)
        {
            nov[v] = false;
            for (int u = 0; u < Size; u++)
            {
                if
                (array[v, u] != 0 && nov[u])
                {
                    Reach(u);
                }
            }
        }

        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 void SearchGm(int k, ref int[] St) //вложенный класс
        {
            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 == 0)
                    {
                        St[k] = j;
                        foreach (int item in St)
                        {
                            Console.Write("{0} ", item + 1);
                        }
                        Console.WriteLine();

                    }
                    else
                    {
                        if (nov[j])
                        {
                            St[k] = j;
                            nov[j] = false;
                            SearchGm(k + 1, ref St);
                            nov[j] = true;
                        }
                    }
                }
            }
        }

        public bool this[int i] //индексатор для обращения к матрице меток
        {
            get
            {
                return nov[i];
            }
            set
            {
                nov[i] = value;
            }
        }

    } //конец вложенного клаcса

    private Node graph; //закрытое поле, реализующее АТД «граф»
    public Graph(string name) //конструктор внешнего класса
    {
        using (StreamReader fileIn = new StreamReader("../../input.txt"))
        {
            int n = int.Parse(fileIn.ReadLine());
            int[,] a = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                string line = fileIn.ReadLine();
                string[] mas = line.Split(' ');
                for (int j = 0; j < n; j++)
                {
                    a[i, j] = int.Parse(mas[j]);
                }
            }
            graph = new Node(a);
        }
    }

    //метод выводит матрицу смежности на консольное окно
    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 Floyd()
    {
        int[,] p;
        long[,] a = graph.Floyd(out p); //запускаем алгоритм Флойда
        int i, j;
        //анализируем полученные данные и выводим их на экран
        for (i = 0; i < graph.Size; i++)
        {
            for (j = 0; j < graph.Size; j++)
            {
                if (i != j)
                {
                    if (a[i, j] == int.MaxValue)
                    {
                        Console.WriteLine("Пути из вершины {0} в вершину {1} не существует", i, j);
                    }
                    else
                    {
                        Console.Write("Кратчайший путь от вершины {0} до вершины {1} равен {2}, ", i, j, a[i, j]);

                        Console.Write(" путь ");
                        Queue items = new Queue();
                        items.Add(i);
                        graph.WayFloyd(i, j, p, ref items);
                        items.Add(j);
                        while (!items.IsEmpty)
                        {
                            Console.Write("{0} ", items.Take());
                        }
                        Console.WriteLine();
                    }
                }
            }
        }
    }

    public void Reachable(int v)
    {
        graph.NovSet();
        Console.Write("Вершины достижимые из {0} вершины: ", v);
        graph.Reach(v);
        for (int i = 0; i < graph.Size; i++)
        {
            if (!graph.NovGet(i) && i != v) //если вершина была просмотрена, то она достижима
            {
                Console.Write("{0} ", i);
            }
        }
        Console.WriteLine();
    }

    public void SearchG() // внешний класс
    {
        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(0, ref a, ref c);
        while (c.Count != 0)
        {
            Console.Write("{0} ", (int)c.Pop() + 1);
        }
    }

    public void SearchGm()//внешний класс
    {
        graph.NovSet();
        int[] St = new int[graph.Size + 1];
        St[0] = 0;
        graph[0] = false; //обращение к индексатору
        graph.SearchGm(1, ref St);
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph graph = new Graph("input.txt");

            graph.SearchGm();
            Console.WriteLine();

            graph.SearchG();

            Console.ReadKey();
        }
    }
}