Laba15

#include <iostream>
#include <string>
#include <clocale>
#include <windows.h>
#include <iomanip>
#include <conio.h>

using namespace std;

int IntInput() // Проверка на Int
{
    int imputNumber;
    while (!(cin >> imputNumber) || (cin.peek() != '\n'))
    {
        cin.clear();
        while (cin.get() != '\n');
        cout << "Это не целое число. Попробуйте еще раз.\n";
    }
    return imputNumber;
}

void main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    cout << "Введите размерность графа: ";
    int N;
    do
    {
        N = IntInput();
        if (N < 1 || N > 21)
        {
            cout << "Число вне допустимых пределов! Повторите ввод числа.";
        }
        else break;
    } while (true);

    typedef int *pInt;
    pInt *W;
    //выделение памяти под динамическую матрицу
    W = new pInt[N];
    for (int i = 0; i < N; i++)
        W[i] = new int[N];

    string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //соответствие именам вершин графа

    cout << "Заполните матрицу связей гарфа (отсутствие связи = 0): " << endl;
    cin.clear();
    cin.sync();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            cout << "Ребро " << str[i] << " - " << str[j] << " : ";
            cin >> W[i][j];
            if (W[i][j] == 0)
                W[i][j] = 999;
        }
        for (int j = 0; j < N; j++)
            if (W[i][j] > 100 || W[i][j] < 0)
                W[i][j] = 999;
    }

    //вывод на экран
    cout << endl << "Весовая матрица:" << endl;
    cout << endl << " ";
    for (int i = 0; i < N; i++)
        cout << "   " << str[i];
    cout << endl << " ";
    for (int i = 0; i < N * 4 + 1; i++)
        cout << "-";
    cout << endl;
    for (int i = 0; i < N; i++)
    {
        cout << str[i] << " |";
        for (int j = 0; j < N; j++)
            if (W[i][j] == 999)
                cout << setw(3) << " " << "|";
            else
                cout << setw(3) << W[i][j] << "|";
        cout << endl << " ";
        for (int q = 0; q < N * 4 + 1; q++)
            cout << "-";
        cout << endl;
    }
    // конец вывода на экран
    int *col = new int[N];
    for (int i = 0; i < N; i++) col[i] = i;
    typedef int *Pint;
    Pint *ostov = new Pint[N - 1];
    for (int i = 0; i < N - 1; i++)
        ostov[i] = new int[2];

    int k, iMin, jMin, minDist, c;

    for (k = 0; k < N - 1; k++)
    {
        // поиск ребра с минимальным весом
        minDist = 99999;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (col[i] != col[j] && W[i][j] < minDist)
                {
                    iMin = i; jMin = j;
                    minDist = W[i][j];
                }
        // добавление ребра в список выбранных
        ostov[k][0] = iMin;
        ostov[k][1] = jMin;
        // перекрашивание вершин
        c = col[jMin];
        for (int i = 0; i < N; i++)
            if (col[i] == c)
                col[i] = col[iMin];
    }

    //Результат
    for (int i = 0; i < N - 1; i++)
        cout << "(" << str[ostov[i][0]] << "," << str[ostov[i][1]] << ")" << endl;

    // очистка памяти
    for (int i = 0; i < N; i++)
        delete[] W[i];
    delete[] W;
    cout << endl << "---Выход - Esc.";
    while (!GetAsyncKeyState(VK_ESCAPE));
}