Detours

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

namespace Graf
{
    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 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 bool[] Reach(int v) //выполняет обход графа в глубину для вершины v, но не выводит просмотренные вершины на экран
            {
                nov[v] = false;
                for (int u = 0; u < Size; u++)
                {
                    if (array[v, u] != 0 && nov[u])
                    {
                        Reach(u);
                    }
                }
                return nov;
            }

            //реализация алгоритма Дейкстры
            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 Add(int v1, int v2) //удалить ребро
            {
                if (array[v1, v2] == 1 || array[v2, v1] == 1)
                {
                    Console.WriteLine("Вершины смежны!");
                }
                else
                {
                    array[v1, v2] = 1;
                    array[v2, v1] = 1;
                    Console.WriteLine("Выполнено");
                }
            }
        }//конец вложенного класса

        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 Reachable(int u) //на основе вспомогательного массива nov выводит на экран истоки
        {
            bool[] used = new bool[graph.Size];
            for (int i = 0; i < graph.Size; i++)
            {
                if (i != u)
                {
                    used = graph.Reach(i);
                    if (used[u] == false)
                    {
                        Console.Write("{0} ", i);
                    }
                }
            }

        }

        // /*/*//*/*//*/*//*/*//*/*//*/*/ ||||| \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\
        public void minDistance(int v)
        {
            graph.NovSet(); //помечаем все вершины графа как непросмотренные
            int[] p;
            long[] d = graph.Dijkstr(v, out p); //запускаем алгоритм Дейкстры

            long min = 99;

            for (int i = 0; i < p.Length; i++)
            {
                if (d[i] < min && d[i] != int.MinValue && d[i] != 0)
                {
                    min = d[i];
                }
            }

            if (min == 99)
            {
                Console.WriteLine("Из заданной вершины другие вершины недостижимы");
            }
            else
            {
                Console.Write("Ближе всего к вершине {0}: ", v);
                for (int i = 0; i < d.Length; i++)
                {
                    if (d[i] == min)
                    {
                        Console.Write("{0} ", i);
                    }
                }
            }
        }

        public void Fount(int v)
        {
            int temp = 0;
            graph.NovSet();//помечаем все вершины графа как непросмотренные
            int[] p;
            long[] d = graph.Dijkstr(v, out p); //запускаем алгоритм Дейкстры
            Console.Write("Вершинa {0} ", v);
            for (int i = 0; i < graph.Size; i++)
            {
                if (i != v)
                {
                    if (d[i] != int.MaxValue)
                    {
                        temp++;
                        Stack items = new Stack();
                        graph.WayDijkstr(v, i, p, ref items);
                    }
                }
            }

            FindFount(temp);
        }

        public void FindFount(int temp)
        {
            if (graph.Size - 1 == temp)
            {
                Console.WriteLine("является истоком");
            }
            else Console.WriteLine("не является истоком");
        }

        public void Add(int v1, int v2) //добавить ребро
        {
            graph.Add(v1, v2);
        }
        // \*\*\\*\*\\*\*\\*\*\\*\*\\*\*\ ||||| /*/*//*/*//*/*//*/*//*/*//*/*/
    }//конец класса Graph

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph("input.txt");
            Console.WriteLine("Graph:");
            g.Show();
            Console.WriteLine();
            /*
            //task_4
            Console.WriteLine("Задайте не смежные вершины");
            Console.WriteLine("Вершина a: ");
            int numA = int.Parse(Console.ReadLine());
            Console.WriteLine("Вершина b: ");
            int numB = int.Parse(Console.ReadLine());
            g.Add(numA, numB);
            g.Show();
            Console.WriteLine();
            */
            /*
            //task 4
            for (int i = 0; i < 5; i++)
            {
                g.Fount(i);
            }
            */
            /*
            //task 16
            Console.WriteLine("Задайте вершину: ");
            int v = int.Parse(Console.ReadLine());
            g.minDistance(v);
            */
            Console.ReadKey();
        }

    }
}