#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <vector>
#include <windows.h>
#include <iomanip>

using namespace std;

struct branch
{
int s;
int e;
int w;
void clear()
{
s=0,e=0,w=0;
}
};

//Функция проверки графа на связность
int isconnected(vector < vector <int> > matrix)
{
    int s = matrix.size(), i=0, j=0, k=0, got=0;
    int * n=new int[s];
    for (i=0; i<s; i++)
    n[i]=0;
    n[0]=1;
    i=0;
    do
    {
    got = 0;
    i++;
    for(j=0;j<s;j++)
        if(n[j]==i)
            for(k=0;k<s;k++)
                if(matrix[j][k]&&!n[k])
                    {
                    got++;
                    n[k]=i+1;
                    }
    }while(got);
    for (i=0; i<s; i++)
        if (!n[i])
            {
             delete[] n;
             return 0;
            }
    delete[] n;
    return 1;
}

//функция для поиска минимального дерева. Результат возвращается в массиве.
vector <branch> tree(vector <vector <int> > weight)
{
    int s = weight.size(), i=0, j=0, k=0, occ=0;
    int * n=new int[s];
    for (i=0; i<s; i++)
        n[i]=0;
    vector<branch> result;
    branch tmp;
    tmp.w = 0;
    //Выбираем наименьшее ребро графа как первую ветвь дерева.
    for(i=0;i<s;i++)
        for(j=i+1;j<s;j++)
            if (weight[i][j]&&((weight[i][j]<tmp.w)||!tmp.w))
                {
                tmp.w = weight[i][j];
                tmp.s=i;
                tmp.e=j;
                }
    result.push_back(tmp);
    //выбрали, сохранили
    n[tmp.s]=1;
    n[tmp.e]=1;
    occ=2;
    //n - массив использованных вершин
    while(occ<s)
    {
    tmp.clear();
    for(i=0;i<s;i++)
        if (n[i]!=0)//Ищем минимальное ребро среди тех, которые образуют дерево при прибавлении к текущему.
            for (j=0;j<s;j++)//Проходимся по вершинам, которые уже в дереве, и ищем ребро, соединённое с ними
               if (weight[i][j]&&((weight[i][j]<tmp.w)||!tmp.w)&&!n[j])
                {
                tmp.w = weight[i][j];
                tmp.s=i;
                tmp.e=j;
                }
    result.push_back(tmp);
    n[tmp.e]=1;
    occ++;
    }
    delete[] n;
    return result;
}

//Подготовка кириллической строки для печать в консоли
string cyr(string str)
{
    char * temp;
    temp=new char[str.size()+1];
    strcpy(temp, str.c_str());
    CharToOem(temp,temp);
    string result = temp;
    delete[] temp;
    return result;
}


int main (void)
{
    string str;
    vector <int> tmpvec;
    vector<branch> tr;
    int n, i, j;
    cout << cyr("Введите количество вершин: ") << endl;
    cin >> n;
    if(n<2)
        {
        cout << cyr("Минимального остовного дерева не существует") << endl;
        system("pause");
        return 0;
        }
    vector <vector <int> > weight(n); //матрица сопряжённости
    cout << cyr("Введите вес ребра между вершинами:")<<endl;
    for (i=0; i<n;i++)
        weight[i].assign(n,0);
    for (i=0;i<n;i++)
        for(j=i;j<n;j++)
            {
             do
             {
             cout<< i+1 << '-' << j+1 << ": ";
             cin >> weight[i][j];
             weight[j][i]=weight[i][j];
             if(weight[i][j]<0) cout << cyr("Неверное значение, повторите ввод:") <<endl;
             }
             while(weight[i][j]<0);
            }
    if (!isconnected(weight))
        {
        cout << cyr("Граф несвязный!")<< endl;
        }
    else
        {
        //если все проверки выполнены, заполняем вектор tr
        tr = tree(weight);
        cout << endl << cyr("Мин. остовное дерево:")<< endl;
        //выводим минимальное остовное дерево в виде таблицы
        cout << cyr("Начало|Конец|Вес")  << endl <<"------|-----|---" <<endl;
        for(i=0;i<tr.size();i++)
            cout << setw(6)<< tr[i].s+1 << "|" << setw(5)<< tr[i].e+1 << "|" << setw(3)<< tr[i].w << endl;
        system("pause");
        return 0;
        }
    system("pause");
    return 1;
}