DM_LR1_v3

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

namespace DM_LR1
{
    class Program
    {
        // ограничения по длине
        const int MIN_LENGTH = 1;
        const int MAX_LENGTH = 100;

        // ограничения значений
        const int MIN_VALUE = -100;
        const int MAX_VALUE = 100;

        // переменные для клики
        public static int n;
        public static int[,] g = new int[20, 20];
        public static int[] res = new int[20];
        public static int[] q = new int[20];
        public static int N_res, i_end;

        static int ReadIntNumber(string stringForUser, int left, int right)
        {
            bool okInput = false;
            int number = MIN_VALUE;
            do
            {
                Console.WriteLine(stringForUser);
                try
                {
                    string buf = Console.ReadLine();
                    number = Convert.ToInt32(buf); // могут возникнуть исключения FormatException, OverflowException
                    if (number >= left && number <= right) okInput = true;
                    else
                    {
                        Console.WriteLine("Некорректное значение! Повторите ввод. ");
                        okInput = false;
                    }
                }

                catch (FormatException)
                {
                    Console.WriteLine("Некорректное значение! Повторите ввод. ");
                    okInput = false;
                }

                catch (OverflowException)
                {
                    Console.WriteLine("Некорректное значение! Повторите ввод. ");
                    okInput = false;
                }

            } while (!okInput);
            return number;
        }

        static void PrintMenu()
        {
            Console.WriteLine("[1]. Алгоритм Шимбелла");
            Console.WriteLine("[2]. Клика (неориентированный граф)");
            Console.WriteLine("[3]. Выделение компонент связности графа");
            Console.WriteLine();
            Console.WriteLine("[4]. Выход");
        }


        static void algShimbella()
        {
            Console.Clear();
            Console.WriteLine("Алгоритм Шимбелла\n");
            int i, j;
            // mas — матрица весов
            int n = ReadIntNumber("Введите размерность матрицы весов: ", MIN_LENGTH, MAX_LENGTH);
            int[,] mas = new int[n, n];
            int[,] mas2 = new int[n, n];

            for (i = 0; i < n; i++)
            {
                for (j = 0; j < n; j++)
                {
                    mas[i, j] = ReadIntNumber("Введите элемент матрицы [" + i + ", " + j + "]:", 0, MAX_LENGTH);
                    mas2[i, j] = mas[i, j];
                }
            }

            int min = 100;
            int max = 0;
            int s = 0;

            int x, h, a, b;
            int[,] massum = new int[n, n];

            int k = ReadIntNumber("Введите число рёбер графа: ", MIN_LENGTH, MAX_LENGTH);
            int t = ReadIntNumber("Какие пути между вершинами показать?\n [1]. Минимальные\n [2]. Максимальные", 1, 2);

            if (t == 1) //Находим минимальные пути
            {
                for (h = 0; h < k - 1; h++)
                {
                    for (i = 0; i < n; i++)
                    {
                        for (x = 0; x < n; x++)
                        {
                            for (j = 0; j < n; j++)
                            {
                                if ((mas[i, j] == 0) || (mas2[j, x] == 0))

                                    s = 0;

                                else
                                {
                                    s = mas[i, j] + mas2[j, x];
                                    if (s <= min)
                                        min = s;
                                }
                            }
                            if (min == 100) { min = 0; }
                            massum[i, x] = min;
                            s = 0;
                            min = 100;

                        }
                    }
                    Console.Write("Матрица для кратчайшего расстояния (количество рёбер: " + (h + 2) + "):\n");
                    for (a = 0; a < n; a++)
                    {
                        for (b = 0; b < n; b++)
                        {
                            Console.Write("{0, 4}", massum[a, b]);
                            mas[a, b] = massum[a, b];
                            massum[a, b] = 0;
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }
            }

            else //Находим максимальные пути
            {
                for (h = 0; h < k - 1; h++)
                {
                    for (i = 0; i < n; i++)
                    {
                        for (x = 0; x < n; x++)
                        {
                            for (j = 0; j < n; j++)
                            {
                                if ((mas[i, j] == 0) || (mas2[j, x] == 0))
                                    s = 0;
                                else
                                {
                                    s = mas[i, j] + mas2[j, x];
                                    if (s >= max)
                                        max = s;
                                }
                            }
                            massum[i, x] = max;
                            s = 0;
                            max = 0;
                        }
                    }
                    Console.Write("Матрица для максимального расстояния (количество рёбер: " + (h + 2) + "):\n");
                    for (a = 0; a < n; a++)
                    {
                        for (b = 0; b < n; b++)
                        {
                            Console.Write("{0, 4}", massum[a, b]);
                            mas[a, b] = massum[a, b];
                            massum[a, b] = 0;
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }
            }
        }

        static void rec(int ii, int N) // рекурсивный алгоритм для клики
        {
            int i, j;
            if (N > N_res) // текущая вершина, последняя результирующая вершина
            {
                for (i = 0; i < i_end; i++)
                    res[i] = q[i];
                N_res = N;
            }

            if (ii == n) // рассмотрена последняя вершина
                return;

            for (i = ii; i < n; i++) // просматриваем вершины от текущей до последней
            {
                for (j = 0; j < i_end; j++)
                    if (g[q[j], i] == 0) // если данная вершина 0, выходим из цикла
                        break;

                if (j == i_end) // последняя вершина, до которой можно дойти
                {
                    q[i_end++] = i;
                    rec(ii + 1, N + 1);
                    i_end--;
                }
                rec(ii + 1, N);
            }
        }

        static void click()
        {
            Console.Clear();
            Console.WriteLine("Клика (неориентированный граф)\n");

            n = ReadIntNumber("Введите количество вершин: ", 1, 20);

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    g[i, j] = ReadIntNumber("Введите элемент матрицы [" + i + ", " + j + "]:", 0, 1);
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    if (g[i, j] == 1) g[j, i] = 1;
            }

            Console.WriteLine("--- Матрица смежности (введёная) ---");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(g[i, j] + " ");
                Console.WriteLine();
            }

            for (int i = 0; i < n; i++) // для каждой вершины вызов функции
            {
                i_end = 0;
                rec(i, 0);
            }

            Console.WriteLine("-------------- Клика ---------------");
            int count = 0;
            Console.Write("Наибольший полный подграф: ");
            for (int i = 0; i < N_res; i++)
            {
                Console.Write(res[i] + 1 + " ");
                count++;
            }
            Console.WriteLine();
            Console.WriteLine("Максимальная клика: " + count + '\n');
        }


        static void component()
        {
            Console.Clear();
            Console.WriteLine("Выделение компонент связности\n");
            int n = ReadIntNumber("Введите количество вершин: ", MIN_LENGTH, MAX_LENGTH);
            int[,] ms = new int[n, n]; // матрица смежности
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    ms[i, j] = ReadIntNumber("Введите элемент [" + i + ", " + j + "]: ", 0, 1);
            }

            Console.WriteLine("--- Матрица смежности (введёная) ---");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(ms[i, j]+ " ");
                Console.WriteLine();
            }
            Console.WriteLine();

            // алгоритм флойда
            int k = 0;
            int n1 = ms.GetLength(0);
            for (k = 0; k < n1; k++)
                for (int i = 0; i < n1; i++)
                    for (int j = 0; j < n1; j++)
                    {
                        ms[i, i] = 1;
                        if (ms[i, k] != 0 && ms[k, j] != 0)
                            if ((ms[i, k] + ms[k, j] < ms[i, j]) || (ms[i, j] == 0))
                                ms[i, j] = 1;
                    }

            Console.WriteLine("------- Матрица достижимости -------");
            for (int i = 0; i < n1; i++)
            {
                for (int j = 0; j < n1; j++)
                    Console.Write(ms[i, j] + " ");
                Console.WriteLine();
            }
            Console.WriteLine();


            Console.WriteLine("---- Матрица сильной связности -----");
            int[,] mss = new int[n, n]; // матрица сильной связности
            for (int i = 0; i < n1; i++)
            { // получаем матрицу сильной связности, умножая матрицу матрицу достижимости на транспонированную матрицу достижимости
                for (int j = 0; j < n1; j++)
                    mss[i, j] = ms[i, j] & ms[j, i];
            }
            for (int i = 0; i < n1; i++)
            {
                for (int j = 0; j < n1; j++)
                    Console.Write(mss[i, j] + " ");
                Console.WriteLine();
            }
            Console.WriteLine();

            int count = 0; //счётчик компонент
            int check = 0;
            int[] kompon = new int[n]; // массив для временного хранения компонент
            for (int a = 0; a < kompon.Length; a++)
                kompon[a] = 0;
            bool[] prov = new bool[n]; // проверка на посещение вершины
            for (int a = 0; a < prov.Length; a++)
                prov[a] = false;

            while (check != n)
            {
                int i = 0;
                int j = 0;
                for(int b = 0; b < prov.Length; b++)
                {
                    if (!prov[b])
                    {
                        i = b;
                        j = b;
                        break;
                    }
                }

                for (; i < n; i++)
                {
                    for (; j < n; j++)
                        if (mss[i, j] == 1 && kompon[j] == 0 && !prov[j])
                        {
                            kompon[j] = j + 1;
                            prov[j] = true;
                        }
                }

                count++;
                Console.Write("Компонента " + count + ": { ");
                for (int a = 0; a < kompon.Length; a++)
                    if (kompon[a] != 0) Console.Write(kompon[a] + " ");
                Console.Write("}");
                Console.WriteLine();

                check++;
                for (int a = 0; a < kompon.Length; a++)
                    kompon[a] = 0;

                int t = 0;
                for (int a = 0; a < prov.Length; a++)
                    if (prov[a]) t++;
                if (t == n) break;
            }
            Console.WriteLine("Количество компонент связности: " + count + '\n');
        }


        static void Main(string[] args)
        {
            int check = 0; // номер пункта меню
            do
            {
                PrintMenu();
                check = ReadIntNumber("", 1, 4); // 4 пункта меню
                switch (check)
                {
                    case 1:
                        algShimbella();
                        break;
                    case 2:
                        click();
                        break;
                    case 3:
                        component();
                        break;
                }
            } while (check < 4);
        }
    }
}