22 - II

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

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 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<int> q = new Queue<int>();
            q.Enqueue(v); //помещаем вершину v в очередь
            nov[v] = false; // помечаем вершину v как просмотренную
            while (q.Count != 0) // пока очередь не пуста
            {
                v = Convert.ToInt32(q.Dequeue()); //извлекаем вершину из очереди
                Console.Write("{0} ", v); //просматриваем ее
                for (int u = 0; u < Size; u++) //находим все вершины
                {
                    if (array[v, u] != 0 && nov[u]) // смежные с данной и еще не просмотренные
                    {
                        q.Enqueue(u); //помещаем их в очередь
                        nov[u] = false; //и помечаем как просмотренные
                    }
                }
            }
        }




        public void SearchGm(int k, ref int[] St, ref bool fl)
        {
            int v = St[k - 1];
            if (!fl)
                return;
            for (int j = 0; j < array.GetLength(0); j++)
            {
                if (array[v, j] != 0)
                {
                    if (k == array.GetLength(0))
                    {
                        St[k] = j;
                        foreach (int item in St)
                        {
                            Console.Write("{0} ", item + 1);
                        }
                        Console.WriteLine();
                        fl = false;
                        return;

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

                }

            }

        }

    } //конец вложенного клаcса
    private Node graph; //закрытое поле, реализующее АТД «граф»
    public Graph(string name) //конструктор внешнего класса
    {
        using (StreamReader file = new StreamReader($"D:/{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 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 SearchGm(int start)//внешний класс Гамильтонов
    {
        graph.NovSet();
        int[] St = new int[graph.Size + 1];
        St[0] = 0;
        graph[0] = false; //обращение к индексатору
        //int start = int.Parse(Console.ReadLine());
        bool fl = true;
        graph.SearchGm(start, ref St, ref fl);
    }

    public int GetLength()
    {
        return graph.Size;
    }
}
class Program
{
    static void Main(string[] args)
    {

        Graph gr = new Graph("input.txt");
        gr.SearchGm(1);
    }

}