Lab3

#include "pch.h"
#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
    setlocale(LC_ALL, (("RUSSIAN")));
    int GRAPH1[9][9] = {
    {0,7,5,0,8,6,0,0,0},
    {7,0,0,2,4,0,0,0,0},
    {5,0,0,0,0,14,0,0,0},
    {0,2,0,0,1,0,10,0,0},
    {8,4,0,1,0,15,2,11,5},
    {6,0,14,0,15,0,0,9,0},
    {0,0,0,10,2,0,0,3,6},
    {0,0,0,0,11,9,3,0,12},
    {0,0,0,0,5,0,6,12,0} };
    int Punkti[9] = { 0,0,0,0,0,0,0,0,0 };
    int Svazi[36];
    int Svazinomera[36];
    int Svazinomera2[9][9];
    int i, j, i1 = 0, i2, t = 0, i0 = 0, a, b,k;
    for (i = 0;i < 9;i++)
    {
        for(j=0;j<9;j++)
        {
            Svazinomera2[i][j] = 0;
        }
    }
    cout << "Вывод матрицы с ценами проезда. Строки - пункт отправления, столбцы - пункт назначения, 0 - дороги нет";
    cout << "\n";
    for (i = 0;i < 9;i++)//Вывод матрицы
        cout << "\t" << "V" << i + 1;
    for (i = 0;i < 9;i++)
    {
        for (j = 0;j < 9;j++)
        {
            if (j == 0) cout << "\nV" << i + 1 << "\t" << GRAPH1[i][j];
            else cout << "\t" << GRAPH1[i][j];
        }
    }//Конец вывода матрицы и поиск элементов остовного дерева
    cout << "\nАлгоритм Крускала" << endl;
    for (i = 0;i < 9;i++)
    {
        for (j = i + 1;j < 9;j++)
        {
            Svazi[i1] = GRAPH1[i][j];
            Svazinomera[i1] = i * 10 + j;
            i1++;
        }
    }
    for (i1 = 0;i1 < 36;i1++)//Вывод полного списка связей между пунктами (если равно 0, то связи нет)
    {
        cout << "\nV" << Svazinomera[i1] / 10 << "-V" << Svazinomera[i1] % 10 << ":\t" << Svazi[i1] << "\t" << Svazinomera[i1];
    }
    for (i = 0;i < 35;i++)
        for (i1 = 0;i1 < 35;i1++)
        {
            if (Svazi[i1] == 0)
            {
                t = Svazi[i1];
                Svazi[i1] = Svazi[i1 + 1];
                Svazi[i1 + 1] = t;
                t = Svazinomera[i1];
                Svazinomera[i1] = Svazinomera[i1 + 1];
                Svazinomera[i1 + 1] = t;
            }
        }
    cout << "\n";
    for (i1 = 0;i1 < 36;i1++)
    {
        if (Svazi[i1] == 0)
        {
            i0++;
        }
    }
    for (i = 0;i < 35 - i0;i++)
        for (i1 = 0;i1 < 35 - i0;i1++)
        {
            if (Svazi[i1] > Svazi[i1 + 1])
            {
                t = Svazi[i1];
                Svazi[i1] = Svazi[i1 + 1];
                Svazi[i1 + 1] = t;
                t = Svazinomera[i1];
                Svazinomera[i1] = Svazinomera[i1 + 1];
                Svazinomera[i1 + 1] = t;
            }
        }
    cout << "\nВывод рёбер";
    for (i1 = 0;i1 < 36 - i0;i1++)//Вывод рёбер, которыми связаны пункты, в порядке увеличения их длины
    {
        cout << "\nV" << Svazinomera[i1] / 10 + 1 << "-V" << Svazinomera[i1] % 10 + 1 << ":\t" << Svazi[i1] << "\t" << Svazinomera[i1] + 11;
    }
    for (i1 = 0;i1 < 36 - i0;i1++)
    {
        k = 0;
        a = Svazinomera[i1] / 10;
        b = Svazinomera[i1] % 10;
        for(j=0;j<9;j++)
        {
            if ((Svazinomera2[a][j] > 0) && (Svazinomera2[j][b] > 0))
            {
                k++;
        } }
        if (((Punkti[a] >=2) && (Punkti[b] >= 1))||((Punkti[a] >= 1)&&(Punkti[b] >= 2))||((Punkti[a] >= 1) && (Punkti[b] >= 1)&&(k>0)))
        {
            Svazi[i1] = 0;
        }
        else
        {
            Punkti[a]++;
            Punkti[b] ++;
            Svazinomera2[a][b]++;
            Svazinomera2[b][a]++;
        }
    }
    for (i = 0;i < 35;i++)
        for (i1 = 0;i1 < 35;i1++)
        {
            if (Svazi[i1] == 0)
            {
                t = Svazi[i1];
                Svazi[i1] = Svazi[i1 + 1];
                Svazi[i1 + 1] = t;
                t = Svazinomera[i1];
                Svazinomera[i1] = Svazinomera[i1 + 1];
                Svazinomera[i1 + 1] = t;
            }
        }
    {for (i0 = 0, i1 = 0;i1 < 36;i1++)
        if (Svazi[i1] == 0)
        {
            i0++;
        }
    }
    cout << "\nЭлементы дерева";//Вывод элементов дерева
    for (i1 = 0;i1 < 36 - i0;i1++)
    {
        cout << "\nV" << Svazinomera[i1] / 10+1 << "-V" << Svazinomera[i1] % 10+1 << ":\t" << Svazi[i1] << "\t" << Svazinomera[i1]+11;
    }

    for (i1=0;i1<9;i1++)
    {
        cout << "\n" << Punkti[i1];
    }
    cout << endl;
    system("pause");
    return 0;
}