//Prufer.h
#ifndef _PRUFER_H_//Страж включения
#define _PRUFER_H_//
 
#include <vector>//Для использования std::vector
#include <iostream>//Для использования потоков ввода/вывода/ошибки
 
class AbstractMatr//Класс-контейнер матрица
{
public:
    AbstractMatr() {}//Конструктор без параметров
    AbstractMatr(size_t n, size_t m);//Конструктор с параметрами размеров
    AbstractMatr(const AbstractMatr&Ob):Matrix(Ob.Matrix) {}//Конструктор копирования. Копируем один вектор в другой
    virtual ~AbstractMatr() {}//Виртуальный деструктор
    void SetSize(size_t n, size_t m);//Функция установки размера
    inline const size_t GetRow() const {return Matrix.size();}//Получение кол-ва строк в векторе
    inline const size_t GetCol() const {return Matrix[0].size();}//Получение кол-ва столбцов в векторе
    void swap(AbstractMatr&);//Меняем местами значения двух объектов.
protected:
    std::vector<std::vector<int> > Matrix;//Вектор векторов типа int. Исходная матрица смежности
};
 
class Prufer:public AbstractMatr//Открытое наследование
{
public:
    Prufer():AbstractMatr() {}//Конструктор без параметров, вызывающий конструктор AbstractMatr()
    Prufer(size_t n, size_t m):AbstractMatr(n, m) {}//Конструктор с параметрами размера, вызывающий констр. AbstractMatr
    Prufer(const AbstractMatr& Ob):AbstractMatr(Ob) {}//Конструктор копирования, вызывающий констр. AbstractMatr
    friend std::ostream& operator <<(std::ostream&, const Prufer&);//Перегрузка оператора вывода в поток
    friend std::istream& operator >>(std::istream&, Prufer&);//Перегрузка оператора ввода в поток
    void Code();//Функция кодирования
    void Decode();//Функция декодирования
    int Degree(int row);//Функция вычисления степени вершины
    int Adjacent(int row);//Функция получения единственной смежной вершины с данной
    bool IsMin(int elem);//Функция проверки на минимальный элемент
    void DeleteEdge(int row, int col);//Функция удаления ребра
    bool IsInPruf(int elem);//Функция проверки на присутствие в коде Прюфера
    bool IsMinNode(int elem, int row);//Функция проверки на минимальный элемент. Для Decode
private:
    std::vector<int> Pruf;//Вектор типа int. Код Прюфера
    std::vector<int> Nodes;//Вектор типа int. Вершины
    std::vector<std::pair<int, int> > Edges;//Вектор типа пары двух интовых значений. Ребра
    std::vector<int> Degrees;//Вектор типа int. Степени
};
 
#endif//

//Prufer.cpp
#include <vector>
#include <algorithm>//Использование стандартных алгоритмов
#include <iostream>
#include <functional>//Использование функторов
#include <stdexcept>//Использование стандартных классов исключений
 
#include "Prufer.h"
 
AbstractMatr::AbstractMatr(size_t n, size_t m)
{
    Matrix.resize(n);//Установка размера исходной матрицы
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);//Установка размера строки исходной матрицы
    }
}
 
void AbstractMatr::SetSize(size_t n, size_t m)
{
    if(GetRow()!=0&&GetCol()!=0)//Если столбцы/строки не равны нулю
        Matrix.clear();//Чистим вектор
    Matrix.resize(n);
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);
    }
}
 
void AbstractMatr::swap(AbstractMatr& Ob)
{
    Matrix.swap(Ob.Matrix);//Меняем местами значения вектора
}
 
void Prufer::Code()
{
    for(int i=0; i!=GetRow(); ++i)
        Nodes.push_back(i+1);//Записываем в вершины элемент i+1
    for(int i=0; i!=GetRow(); ++i)
        Degrees.push_back(Degree(Nodes[i]-1));//Записываем в степени степень i элемента вектора Nodes - 1
    for(int t=0; t!=GetRow()-2; ++t)//От 0 до N-2
    {
        //Проверка на то, что наличие листьев
        if(std::count_if(Degrees.begin(), Degrees.end(), std::bind2nd(std::equal_to<int>(), 1))==0)
        {
            std::cout<<"On "<< t+1 <<" step\n";//Пишем на каком шаге
            //Кидаем исключение, которое будет обработано в main(). Используем стандартный класс
            //std::invalid_argument
            throw std::invalid_argument("Can`t code this graph (tree). There are no nodes with degree 1\n");
        }
        for(int i=0; i!=Nodes.size(); ++i)//От 0 до размера вектора вершин
        {
            if(Degrees[i]==1)//Если i-ая вершина - лист
            {
                if(IsMin(Nodes[i]))//Если i-ая вершина минимальна
                {
                    int Adj=Adjacent(Nodes[i]-1);//Возвращаем смежную с i-1 вершиной вершину
                    Pruf.push_back(Adj+1);//Добавляем в вектор кода Прюфера, смежную вершину+1
                    DeleteEdge(Nodes[i]-1, Adj);//Удаляем ребро Nodes[i]-1, Adj
                    //Удаляем из вектора вершин i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Degrees.clear();//Очищаем вектор степеней
                    for(int i=0; i!=Nodes.size(); ++i)
                    {
                        Degrees.push_back(Degree(Nodes[i]-1));//Заполняем вектор степеней
                    }
                    break;//Брякаем цикл
                }
            }
        }
    }
    Edges.push_back(std::make_pair<int, int>(Nodes[0], Nodes[1]));//Записываем ребро Nodes[0]->Nodes[1] в вектор ребер
    std::cout<<"Prufer`s code\n";//Вывод в консоль строки
    std::copy(Pruf.begin(), Pruf.end(), std::ostream_iterator<int>(std::cout, " "));//Вывод в консоль вектора
    std::cout<<std::endl;//Перевод каретки+очистка буфера
}
 
void Prufer::Decode()
{
    std::pair<int, int> Temp;//Создаем временный элемент типа пары двух интовых значений
    Temp=Edges.front();//Записываем первый элемент из вектора ребер во временный элемент
    Edges.clear();//Чистим вектор ребер
    Nodes.clear();//Чистим вектор вершин
    for(int i=0; i!=Matrix.size(); ++i)
        Nodes.push_back(i+1);//Записываем i+1 вершину (дабы начиналось с 1)
    for(int t=0; t!=GetRow()-2; ++t)//До N-2
    {
        for(int i=0; i!=Nodes.size(); ++i)
        {
            if(!IsInPruf(Nodes[i]))//Если не i-тая вершина не выходит в код прюфера
            {
                if(IsMinNode(Nodes[i], i))//И если она минимальная среди вершин
                {
                    //Делаем пару интовых значений. Первый элемент вектора Прюфера и i-тую вершину.
                    //Записываем ее в вектор ребер
                    Edges.push_back(std::make_pair<int, int>(Pruf[0], Nodes[i]));
                    //Удаляем i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Pruf.erase(std::find(Pruf.begin(), Pruf.end(), Pruf[0]));//Удаляем первый элемент из в. Прюфера
                    break;//Брякаем
                }
            }
        }
    }
    Edges.push_back(Temp);//Записываем в конец вектора значение, записанное во временной переменной
    std::cout<<"Decode from Prufers`s code\nDefault tree\n";//Вывод строки
    //Цикл по итератору. От начала вектора ребер, до конца.
    for(std::vector<std::pair<int, int> >::const_iterator Iter=Edges.begin(); Iter!=Edges.end(); ++Iter)
    {
        std::cout<<"<"<<Iter->first<<','<<Iter->second<<'>'<<'\n';//Выводим в консоль <вершина из прюфера, вершина из nodes>
    }
}
 
int Prufer::Degree(int row)
{
    int cnt=0;//Счетчик
    for(int j=0; j!=GetCol(); ++j)//До кол-ва столбцов
    {
        if(Matrix[row][j]==1)//Если j-ый элемент строки row равен 1
            cnt++;//Плюсуем счетчик
    }
    return cnt;
}
 
int Prufer::Adjacent(int row)
{
    int i;
    for(i=0; i!=GetCol(); ++i)
        if(Matrix[row][i]==1)//Если i-ый элемент строки row равен 1
            break;//Брякаем
    return i;//Вернули i
}
 
bool Prufer::IsMin(int elem)
{
    int min=elem;//min=elem
    for(int i=0; i!=Degrees.size(); ++i)
    {
        if(Degrees[i]==1)//Если i-ая степень=1 
        {
            if(Nodes[i]<min)//Если i-ая вершина меньше минимума
                min=Nodes[i];//Минимум становится равен i-ой вершине
        }
    }
    return (min==elem);//Если min==elem возвращаем true, иначе false
}
 
void Prufer::DeleteEdge(int row, int col)
{
    Matrix[row][col]=0;//col-тый элемент в row-той строке равен 0
    Matrix[col][row]=0;//наоборот
}
 
std::ostream& operator <<(std::ostream& os, const Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        //Вывод на экран. Стандартный алгоритм copy
        std::copy(Ob.Matrix[i].begin(), Ob.Matrix[i].end(), std::ostream_iterator<int>(os, " "));
        os<<'\n';
    }
    return os;
}
 
std::istream& operator >>(std::istream& is, Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        for(int j=0; j!=Ob.GetCol(); ++j)
        {
            if(i>=j)//Если i>=j переходим к след итерации
                continue;
            std::cout<<"Enter 1 for connect "<< i+1 <<" and "<< j+1 <<" nodes, and 0 for not\n";
            is>>Ob.Matrix[i][j];
            if(i!=j)//Если i!=j
                Ob.Matrix[j][i]=Ob.Matrix[i][j];//
        }
    }
    return is;
}
 
bool Prufer::IsInPruf(int elem)
{
    for(int i=0; i!=Pruf.size(); ++i)
    {
        if(elem==Pruf[i])//Если элемент = Pruf[i]
        {
            return true;//Вернули true. То есть элемент присутствует в Прюфере
        }
    }
    return false;//Вернули false. Элемента нет. Все гуд
}
 
bool Prufer::IsMinNode(int elem, int row)
{
    int min=elem;//Минимум = элемент
    for(int i=row; i!=Nodes.size(); ++i)//От номера элемента в массиве до конца
    {
        if(Nodes[i]<min)
            min=Nodes[i];
    }
    return (min==elem);
}

//Main.cpp
#include <iostream>
 
#include "Prufer.h"
 
int main()
{
    Prufer Ob;//Создали объект
    int N;
    std::cout<<"Enter N: ";
    std::cin>>N;//Ввели размер
    Ob.SetSize(N, N);//Установили размер для квадратной матрицы
    std::cout<<"Enter matrix\n";
    std::cin>>Ob;//Ввели матрицу
    std::cout<<"Initial matrix\n";
    std::cout<<Ob;//Вывели матрицу
    try//Блок try, catch
    {
        Ob.Code();//Вызвали кодирование. Если в функции кинулось исключение - перешли в блок catch
        Ob.Decode();//Если нет - декодируем дерево
    }
    catch(const std::invalid_argument& e)//Ловим исключение типа const std::invalid_argument&
    {
        std::cout<<e.what()<<'\n';//what - функция класса invalid_argument.
    }
    system("pause");//Для release версии
    return 0;
}