#include <stdio.h>
#include <conio.h>
#include <Windows.h>

#include <string>
#include <locale>

#include <stack>
#include <vector>
#include <algorithm>
#include <cctype>


bool iswm(std::string const &_sMask, std::string const &_Text)
{
    std::string sMask;

    {
        char cLast = 0;
        size_t iLast = 0;

        for (size_t i = 0; i < _sMask.size(); i++)
        {
            char c = _sMask[i];
            if (!(cLast == c && c == '*' || !isgraph(c)))
            {
                sMask.push_back(_sMask[i]);
                iLast++;
            }

            cLast = c;
        }
    }

    // вектор состояний, хранятся позиции состояния(т.е. символа)
    std::vector<size_t> States(1, -1);

    // идём чётко по тексту
    for (char cSource : _Text)
    {
        // быстрый выход по несоответствию
        if (States.empty())
            break;

        std::vector<size_t> NewStates;

        // но по маске не идём, проход по маске представляет НКА!
        for (size_t iPos : States)
        {
            if (sMask[iPos + 1] == '?' || sMask[iPos + 1] == cSource)
            {
                NewStates.push_back(iPos + 1);
            }

            // если текущий переход *, то остаёмся тут и всё
            if (iPos != -1 && sMask[iPos] == '*')
            {
                NewStates.push_back(iPos);
            }

            if (sMask[iPos + 1] == '*')
            {
                NewStates.push_back(iPos + 1);

                // * = 0
                if (iPos + 2 < sMask.size() && (sMask[iPos + 2] == '?' || sMask[iPos + 2] == cSource))
                {
                    NewStates.push_back(iPos + 2);
                }
            }
        }

        States.assign(NewStates.begin(), NewStates.end());
    }


    // допускающее - последнее ) естессно
    for (size_t i : States)
    {
        if (i == sMask.size() - 1)
        {
            return true;
        }
    }

    return false;
}

enum class E_ERROR
{
    NONE = -1,
    NOT_SETTED_TYPE,
    WHERE_IS_FILE,
    PARSING_ERROR,
    BROKEN_DATA
};

enum class E_GRAPHS_REPRES
{
    NONE = -1,
    ADJ_LIST,
    ADJ_MAT,
    INC_MAT
};

struct CEdge;
struct CVertex
{
    CVertex()
    {
    }

    std::vector<CEdge *> Edges;

    bool bIsVisited = false;
    bool bIsInGraph = false;

    DWORD dwID = -1;

    void *pMyData = nullptr;
};

struct CEdge
{
    CEdge()
    {
    }

    DWORD dwID = -1;

    CVertex *pV1 = nullptr;
    CVertex *pV2 = nullptr;

    float fWeight = 1.0f;

    bool bIsVisited = false;

    bool bIsInGraph = false;

    //void *pMyData = nullptr;
};

class CGraph
{
public:
    CGraph() :
        m_eReprType(E_GRAPHS_REPRES::NONE), m_bIsLoaded(false), m_bIsParsing(false)
    {
    }

    CGraph(CGraph const &_Graph) :
        m_bIsLoaded(false)
    {
        if (this != &_Graph)
        {
            for (auto iV : _Graph.m_Vertices)
            {
                //CVertex *pNew = new CVertex(*iV);

                //pNew->pMyData = iV->pMyData;

                m_Vertices.push_back(iV);
            }

            for (auto iE : _Graph.m_Edges)
            {
                //m_Edges.push_back(new CEdge(*iE));
                m_Edges.push_back(iE);
            }

            m_eReprType = _Graph.m_eReprType;
            m_bIsOriented = _Graph.m_bIsOriented;
            m_bIsWeighted = _Graph.m_bIsWeighted;
            m_bIsLoaded = _Graph.m_bIsLoaded;
            m_bIsParsing = _Graph.m_bIsParsing;
        }
    }

    CGraph(E_GRAPHS_REPRES const _Repr) :
        m_eReprType(_Repr), m_bIsLoaded(false), m_bIsParsing(false)
    {
    }

    ~CGraph()
    {

    };

    int GetEdgeID(int _nVertex1, int _nVertex2) const
    {
        if (!m_bIsLoaded && !m_bIsParsing)
            return INT_MAX;

        CVertex *v = m_Vertices[_nVertex1];

        if (!v->bIsInGraph)
            return INT_MAX;

        for (auto e : v->Edges)
        {
            if (!e->bIsInGraph)
                continue;

            if (e->pV1->dwID == _nVertex1 && e->pV2->dwID == _nVertex2)
                return e->dwID;

            if (e->pV1->dwID == _nVertex2 && e->pV2->dwID == _nVertex1)
                return e->dwID;
        }

        return INT_MAX;
    }

    /*
    Format of file:

        repres_type(E_GRAPHS_STRUCT) is_oriented(0, 1) is_weighted(0, 1)
        VertexCount EdgeCount

        representation:
            adj_list:
                vert0 -> vert1(weight1), vert2(weight2)
                vert0 -> vert1, vert2

            adj_mat:
                vert to vert mat(weigth)
                vert to vert mat

            inc_mat:
                vert to edge mat

    */

    E_ERROR ParseFile(std::string const &_sFileName)
    {
        m_bIsLoaded = false;
        m_bIsParsing = true;

        //if (m_eReprType == E_GRAPHS_REPRES::NONE)
        //  return E_ERROR::NOT_SETTED_TYPE;

        if (_sFileName.empty())
            return E_ERROR::WHERE_IS_FILE;

        FILE *pFile;

        fopen_s(&pFile, _sFileName.c_str(), "r");

        if (!pFile)
            return E_ERROR::WHERE_IS_FILE;

        // read the type of graph
        // mask: repres_type(E_GRAPHS_REPRES) is_oriented(0, 1) is_weighted(0, 1)

        int eReprType, bIsOriented, bIsWeighted;

        if (fscanf_s(pFile, "%d %d %d", &eReprType, &bIsOriented, &bIsWeighted) != 3)
            return E_ERROR::PARSING_ERROR;

        m_eReprType = (E_GRAPHS_REPRES)eReprType;
        m_bIsOriented = (bIsOriented != 0);
        m_bIsWeighted = (bIsWeighted != 0);

        int nVertexCount = -1;

        // read the count of objects
        // mask: VertexCount EdgeCount

        if (fscanf_s(pFile, "%d", &nVertexCount) != 1)
            return E_ERROR::PARSING_ERROR;

        m_Vertices.resize(nVertexCount);
        for (int i = 0; i < nVertexCount; i++)
        {
            m_Vertices[i] = new CVertex;
        }

        // read the repres of graph
        // mask: vert0 -> vert1, vert2, ...,
        // weighted mask: vert0 -> vert1(weight1), vert2(weight2), ...,
        if (m_eReprType == E_GRAPHS_REPRES::ADJ_LIST)
        {
            while (1)
            {
                int nFID;

                if (fscanf_s(pFile, "%d -> ", &nFID) != 1)
                    goto end;

                if (nFID < 0 || nFID >= nVertexCount)
                    return E_ERROR::BROKEN_DATA;

                m_Vertices[nFID]->dwID = nFID;
                m_Vertices[nFID]->bIsInGraph = true;

                if (m_bIsWeighted)
                {
                    float fWeight;
                    int nSID;

                    char c;
                    while (fscanf_s(pFile, "%d(%f)%c", &nSID, &fWeight, &c) == 3)
                    {
                        if (nSID < 0 || nSID >= nVertexCount)
                            return E_ERROR::BROKEN_DATA;

                        m_Vertices[nSID]->bIsInGraph = true;
                        m_Vertices[nSID]->dwID = nSID;

                        CEdge *pEdge = new CEdge;
                        pEdge->bIsInGraph = true;
                        pEdge->fWeight = fWeight;
                        pEdge->pV1 = m_Vertices[nFID];
                        pEdge->pV2 = m_Vertices[nSID];
                        pEdge->dwID = m_Edges.size();

                        m_Vertices[nSID]->Edges.push_back(pEdge);
                        m_Vertices[nFID]->Edges.push_back(pEdge);

                        m_Edges.push_back(pEdge);

                        if (c != ',')
                            break;
                    }
                }
                else
                {
                    int nSID;

                    char c;
                    while (fscanf_s(pFile, "%d%c", &nSID, &c) == 2)
                    {
                        if (nSID < 0 || nSID >= nVertexCount)
                            return E_ERROR::BROKEN_DATA;

                        CEdge *pEdge = new CEdge;
                        pEdge->bIsInGraph = true;
                        pEdge->pV1 = m_Vertices[nFID];
                        pEdge->pV2 = m_Vertices[nSID];
                        pEdge->dwID = m_Edges.size();

                        m_Vertices[nSID]->Edges.push_back(pEdge);
                        m_Vertices[nFID]->Edges.push_back(pEdge);

                        m_Edges.push_back(pEdge);

                        if (c != ',')
                            break;
                    }
                }
            }
        }
        else if (m_eReprType == E_GRAPHS_REPRES::ADJ_MAT)
        {
            m_Vertices.resize(nVertexCount);
            for (int i = 0; i < nVertexCount; i++)
            {
                m_Vertices[i] = new CVertex;
            }

            // цикл по кол-ву вершин, читаем по одному числу
            for (int v = 0; v < nVertexCount; v++)
            {
                CVertex *V1 = m_Vertices[v];
                V1->bIsInGraph = true;

                for (int v2 = 0; v2 < nVertexCount; v2++)
                {
                    CVertex *V2 = m_Vertices[v2];
                    V2->bIsInGraph = true;

                    if (m_bIsWeighted)
                    {
                        int nAdj;
                        float fWeight;

                        if (fscanf_s(pFile, "%d(%f)", &nAdj, &fWeight) != 2)
                            return E_ERROR::PARSING_ERROR;

                        if (nAdj == 1)
                        {
                            // из v в v2

                            CEdge *pEdge = new CEdge;
                            pEdge->bIsInGraph = true;
                            pEdge->fWeight = fWeight;
                            pEdge->pV1 = V1;
                            pEdge->pV2 = V2;
                            pEdge->dwID = m_Edges.size();

                            V1->Edges.push_back(pEdge);
                            V2->Edges.push_back(pEdge);

                            m_Edges.push_back(pEdge);
                        }
                    }
                    else
                    {
                        int nAdj;

                        if (fscanf_s(pFile, "%d", &nAdj) != 1)
                            return E_ERROR::PARSING_ERROR;

                        if (nAdj == 1)
                        {
                            // из v в v2

                            CEdge *pEdge = new CEdge;
                            pEdge->bIsInGraph = true;
                            pEdge->pV1 = V1;
                            pEdge->pV2 = V2;
                            pEdge->dwID = m_Edges.size();

                            V1->Edges.push_back(pEdge);
                            V2->Edges.push_back(pEdge);

                            m_Edges.push_back(pEdge);
                        }
                    }
                }
            }
        }
        /*
        else if (m_eReprType == E_GRAPHS_REPRES::INC_MAT)
        {
            for (int v = 0; v < nVertexCount; v++)
            {
                for (int e = 0; e < nEdgeCount; e++)
                {
                    int nAdj;

                    if (fscanf_s(pFile, "%d", &nAdj) != 1)
                        return E_ERROR::PARSING_ERROR;

                    if (m_bIsOriented)
                    {
                        // значит, что ребро уходит из вершины
                        if (nAdj == -1)
                        {
                            m_Vertices[v].bIsInGraph = true;
                            m_Vertices[v].Edges.push_back(e);

                            m_Edges[e].bIsInGraph = true;
                            m_Edges[e].fWeight = 1.0f;
                            m_Edges[e].nFirstVertexID = v;
                        }
                        else if (nAdj == 1)
                        {
                            m_Vertices[v].bIsInGraph = true;
                            m_Vertices[v].Edges.push_back(e);

                            m_Edges[e].bIsInGraph = true;
                            m_Edges[e].fWeight = 1.0f;
                            m_Edges[e].nSecondVertexID = v;
                        }
                    }
                    else if (nAdj == 1)
                    {
                        m_Vertices[v].bIsInGraph = true;
                        m_Vertices[v].Edges.push_back(e);

                        m_Edges[e].bIsInGraph = true;
                        m_Edges[e].fWeight = 1.0f;

                        // если первая вершина уже стоит(не -1), то ставим вторую
                        if (m_Edges[e].nFirstVertexID == -1)
                            m_Edges[e].nFirstVertexID = v;
                        else
                            m_Edges[e].nSecondVertexID = v;
                    }
                }
            }
        }
        */

end:
        fclose(pFile);

        m_bIsParsing = false;
        m_bIsLoaded = true;

        return E_ERROR::NONE;
    }

    template<class fn>
    void DFS_Rec(CVertex *pVertex, fn &_Func)
    {
        //_Func(pVertex);
        PrintVInfo(pVertex);

        // ставим метку, что посетили данную вершину
        pVertex->bIsVisited = true;

        if (m_bIsOriented)
        {
            // проходим по все ребрам
            for (auto e : pVertex->Edges)
            {
                // смотрим были ли мы в вершине соседней раньше
                // если нет, то запускаемся из нее
                if (e->pV1 == pVertex && !e->pV2->bIsVisited)
                {
                    DFS_Rec(e->pV2, _Func);
                }
            }
        }
        else
        {
            // проходим по все ребрам
            for (auto e : pVertex->Edges)
            {
                // смотрим были ли мы в вершине соседней раньше
                // если нет, то запускаемся из нее
                if (!e->pV2->bIsVisited)
                {
                    DFS_Rec(e->pV2, _Func);
                }

                if (!e->pV1->bIsVisited)
                {
                    DFS_Rec(e->pV1, _Func);
                }
            }
        }
    }

    template<class fn>
    void DFS(fn &_Func)
    {
        DFS_Rec(m_Vertices[0], _Func);

        for (CVertex *iVer : m_Vertices)
            iVer->bIsVisited = false;
    }

    void PrintVInfo(CVertex *pVertex) const
    {
        printf("Edges of vertex %d:\n", pVertex->dwID);

        for (auto iEdge : pVertex->Edges)
        {
            if (m_bIsWeighted)
            {
                printf("Edge %d: %d -> %d\n",
                    iEdge->dwID,
                    iEdge->pV1->dwID,
                    iEdge->pV2->dwID);
            }
            else
            {
                printf("Edge %d(%0.3f): %d -> %d\n",
                    iEdge->dwID,
                    iEdge->fWeight,
                    iEdge->pV1->dwID,
                    iEdge->pV2->dwID);
            }
        }

        printf("\n");
    }

    std::vector<CVertex *> const &GetVertices() const
    {
        return m_Vertices;
    };

    std::vector<CVertex *> &GetVertices()
    {
        return m_Vertices;
    };

    std::vector<CEdge *> const &GetEdges() const
    {
        return m_Edges;
    };

    std::vector<CEdge *> &GetEdges()
    {
        return m_Edges;
    };

    bool                    m_bIsOriented;
    bool                    m_bIsWeighted;
private:
    std::vector<CVertex *>  m_Vertices;
    std::vector<CEdge *>    m_Edges;
    E_GRAPHS_REPRES         m_eReprType;

    bool                    m_bIsLoaded;
    bool                    m_bIsParsing;
};

/*
template <typename T, typename R, typename ...Args>
R proxycall(T & obj, R (T::*mf)(Args...), Args &&... args)
{
    return (obj.*mf)(std::forward<Args>(args)...);
}
*/

void PrintError(E_ERROR const &er)
{
    switch (er)
    {
    case E_ERROR::BROKEN_DATA:
        printf("Error!!! Data is broken!\n");
        break;
    case E_ERROR::NOT_SETTED_TYPE:
        printf("Error!!! Type of graph wasn't setted!\n");
        break;
    case E_ERROR::PARSING_ERROR:
        printf("Error!!! Parser error!\n");
        break;
    case E_ERROR::WHERE_IS_FILE:
        printf("Error!!! Smth with file(Busy, not finded)!\n");
        break;
    }
}

#define V_RET(v) \
    if ((hr = v) != E_ERROR::NONE) \
    { \
        PrintError(hr); \
    } \

DWORD DSUGet(DWORD const _dwVertexID, std::vector<CVertex *> &_Vertices)
{
    if (_dwVertexID == *(DWORD *)_Vertices.at(_dwVertexID)->pMyData)
        return _dwVertexID;

    *(DWORD *)_Vertices.at(_dwVertexID)->pMyData = DSUGet(*(DWORD *)_Vertices.at(_dwVertexID)->pMyData, _Vertices);
    return *(DWORD *)_Vertices.at(_dwVertexID)->pMyData;
}

void RunKruskal()
{
    CGraph graph;

    E_ERROR hr;

    V_RET(graph.ParseFile("adj_mat.txt"));

    DWORD dwTreeID = 0;
    for (auto iVertex : graph.GetVertices())
    {
        iVertex->pMyData = new DWORD;
        iVertex->dwID = dwTreeID;
        *((DWORD *)iVertex->pMyData) = dwTreeID++;
    }

    graph.DFS([](int const nid) { printf("%d\n", nid); });

    sort(graph.GetEdges().begin(), graph.GetEdges().end(),
        [](CEdge const *const _p1, CEdge const *const _p2)
    {
        return _p1->fWeight < _p2->fWeight;
    });

    CGraph SpanningGraph(graph);
    SpanningGraph.GetEdges().clear();

    auto Vertices = graph.GetVertices();

    for (auto iEdge : graph.GetEdges())
    {
        CVertex *V1 = Vertices.at(DSUGet(iEdge->pV1->dwID, Vertices));
        CVertex *V2 = Vertices.at(DSUGet(iEdge->pV2->dwID, Vertices));

        if (V1->dwID != V2->dwID)
        {
            if (rand() & 1)
                *(DWORD *)V2->pMyData = *(DWORD *)V1->pMyData;
            else
                *(DWORD *)V1->pMyData = *(DWORD *)V2->pMyData;

            SpanningGraph.GetEdges().push_back(iEdge);
        }
    }

    printf("\n\n\nSpanning graph:\n\n");

    for (auto iEdge : SpanningGraph.GetEdges())
    {
        printf("%d %d\t %0.2f\n", iEdge->pV1->dwID, iEdge->pV2->dwID, iEdge->fWeight);
    }

    //SpanningGraph.DFS([](int const nid) { printf("%d\n", nid); });
}

void RunPrima()
{
    CGraph graph;

    E_ERROR hr;

    V_RET(graph.ParseFile("adj_mat.txt"));

    graph.DFS([](int const nid) { printf("%d\n", nid); });

    CGraph SpanningGraph(graph);
    SpanningGraph.GetEdges().clear();

    // говорим графу, что каждое ребро не было добавлено
    for (auto iVertex : graph.GetVertices())
    {
        iVertex->pMyData = new bool;
        *((bool *)iVertex->pMyData) = false;
    }

    // добавляем первое ребро(типо случайное)
    CEdge *pStartMinEdge = nullptr;

    DWORD dwRandVertex = rand() % graph.GetVertices().size();
    for (auto iEdge : graph.GetVertices()[dwRandVertex]->Edges)
    {
        // если обе вершины заняты, выходим
        if (*(bool *)iEdge->pV1->pMyData && *(bool *)iEdge->pV2->pMyData)
            continue;

        // если не в конечном графе и по весу подходит:
        if (!pStartMinEdge || pStartMinEdge->fWeight > iEdge->fWeight)
        {
            pStartMinEdge = iEdge;
        }
    }

    SpanningGraph.GetEdges().push_back(pStartMinEdge);
    *(bool *)pStartMinEdge->pV1->pMyData = true;
    *(bool *)pStartMinEdge->pV2->pMyData = true;

    for (DWORD i = 0; i < SpanningGraph.GetVertices().size() - 2; i++)
    {
        CEdge *pMinEdge = nullptr;

        // ищем ребро с наименьшим весом во всех рёбрах,
        //      которые касаются конечного графа,
        //      но не в нём

        for (auto iEdge : SpanningGraph.GetEdges())
        {
            // проходимся по всем рёбрам из вершины V1:
            for (auto iV1Edge : iEdge->pV1->Edges)
            {
                // если обе вершины заняты, выходим
                if (*(bool *)iV1Edge->pV1->pMyData && *(bool *)iV1Edge->pV2->pMyData)
                    continue;

                // если не в конечном графе и по весу подходит:
                if (!pMinEdge || pMinEdge->fWeight > iV1Edge->fWeight)
                {
                    pMinEdge = iV1Edge;
                }
            }

            // проходимся по всем рёбрам из вершины V2:
            for (auto iV2Edge : iEdge->pV2->Edges)
            {
                // если обе вершины заняты, выходим
                if (*(bool *)iV2Edge->pV1->pMyData && *(bool *)iV2Edge->pV2->pMyData)
                    continue;

                // если не в конечном графе и по весу подходит:
                if (!pMinEdge || pMinEdge->fWeight > iV2Edge->fWeight)
                {
                    pMinEdge = iV2Edge;
                }
            }
        }

        // теперь в графе
        *(bool *)pMinEdge->pV1->pMyData = true;
        *(bool *)pMinEdge->pV2->pMyData = true;

        SpanningGraph.GetEdges().push_back(pMinEdge);
    }

    printf("\n\n\nSpanning graph:\n\n");

    for (auto iEdge : SpanningGraph.GetEdges())
    {
        printf("%d %d\t %0.2f\n", iEdge->pV1->dwID, iEdge->pV2->dwID, iEdge->fWeight);
    }
}

void RunBoruvka()
{
    struct CBoruvkaInfo
    {
        DWORD dwSize;
        DWORD dwRoot;
        CEdge *pClosest;
    };

    CGraph graph;

    E_ERROR hr;

    V_RET(graph.ParseFile("adj_mat.txt"));

    //graph.DFS([](int const nid) { printf("%d\n", nid); });

    CGraph SpanningGraph(graph);
    SpanningGraph.GetEdges().clear();

    // каждая вершина хранит номер своего дерева
    // в начале - дерево = вершина
    DWORD dwTreeID = 0;
    for (auto iVertex : SpanningGraph.GetVertices())
    {
        iVertex->pMyData = new CBoruvkaInfo;
        ((CBoruvkaInfo *)iVertex->pMyData)->dwRoot = dwTreeID++;
        ((CBoruvkaInfo *)iVertex->pMyData)->dwSize = 1;
    }

    auto _FindRoot = [&SpanningGraph](DWORD i)
    {
        while (i != ((CBoruvkaInfo *)SpanningGraph.GetVertices()[i]->pMyData)->dwRoot)
        {
            i = ((CBoruvkaInfo *)SpanningGraph.GetVertices()[i]->pMyData)->dwRoot;
        }

        return i;
    };

    while (SpanningGraph.GetEdges().size() < SpanningGraph.GetVertices().size() - 1)
    {
        for (auto iVertex : SpanningGraph.GetVertices())
        {
            ((CBoruvkaInfo *)iVertex->pMyData)->pClosest = nullptr;
        }

        for (auto iEdge : graph.GetEdges())
        {
            DWORD i = _FindRoot(iEdge->pV1->dwID);
            DWORD j = _FindRoot(iEdge->pV2->dwID);

            CVertex *vi = SpanningGraph.GetVertices()[i];
            CVertex *vj = SpanningGraph.GetVertices()[j];

            if (i == j)
                continue;

            if (!((CBoruvkaInfo *)vi->pMyData)->pClosest || iEdge->fWeight < ((CBoruvkaInfo *)vi->pMyData)->pClosest->fWeight)
            {
                ((CBoruvkaInfo *)vi->pMyData)->pClosest = iEdge;
            }

            if (!((CBoruvkaInfo *)vj->pMyData)->pClosest || iEdge->fWeight < ((CBoruvkaInfo *)vj->pMyData)->pClosest->fWeight)
            {
                ((CBoruvkaInfo *)vj->pMyData)->pClosest = iEdge;
            }
        }

        for (auto iVertex : SpanningGraph.GetVertices())
        {
            CEdge *pEdge = ((CBoruvkaInfo *)iVertex->pMyData)->pClosest;

            if (!pEdge)
                continue;

            DWORD u = _FindRoot(pEdge->pV1->dwID);
            DWORD v = _FindRoot(pEdge->pV2->dwID);

            if (u != v)
            {
                CVertex *vu = SpanningGraph.GetVertices()[u];
                CVertex *vv = SpanningGraph.GetVertices()[v];

                if (((CBoruvkaInfo *)vu->pMyData)->dwSize < ((CBoruvkaInfo *)vv->pMyData)->dwSize)
                {
                    ((CBoruvkaInfo *)vu->pMyData)->dwRoot = v;
                    ((CBoruvkaInfo *)vv->pMyData)->dwSize += ((CBoruvkaInfo *)vu->pMyData)->dwSize;
                }
                else
                {
                    ((CBoruvkaInfo *)vv->pMyData)->dwRoot = u;
                    ((CBoruvkaInfo *)vu->pMyData)->dwSize += ((CBoruvkaInfo *)vv->pMyData)->dwSize;
                }

                SpanningGraph.GetEdges().push_back(pEdge);
            }
        }
    }

    printf("\n\n\nSpanning graph:\n\n");

    for (auto iEdge : SpanningGraph.GetEdges())
    {
        printf("%d %d\t %0.2f\n", iEdge->pV1->dwID, iEdge->pV2->dwID, iEdge->fWeight);
    }
}

void RunRid()
{
    CGraph graph;

    E_ERROR hr;

    V_RET(graph.ParseFile("adj_mat.txt"));

    CVertex *pStartV = nullptr;
    DWORD dwCountOfOdd = 0;

    for (auto iV : graph.GetVertices())
    {
        if ((iV->Edges.size() % 2) == 1)
        {
            dwCountOfOdd++;
            pStartV = iV;
        }
    }

    if (dwCountOfOdd != 2 && dwCountOfOdd != 0)
        return;

    if (dwCountOfOdd == 0)
    {
        pStartV = graph.GetVertices()[1];
    }

    //graph.DFS([](int const nid) { printf("%d\n", nid); });

    CGraph EulerGraph(graph);
    EulerGraph.GetEdges().clear();
    EulerGraph.GetVertices().clear();

    std::stack<CVertex *> st;
    st.push(pStartV);

    auto _DelEdge = [](CVertex *_pVertex, CEdge *_pEdge)
    {
        for (DWORD i = 0; i < _pVertex->Edges.size(); i++)
        {
            CEdge *pEdge = _pVertex->Edges[i];

            if (pEdge == _pEdge)
            {
                _pVertex->Edges.erase(_pVertex->Edges.begin() + i);

                break;
            }
        }
    };

    while (!st.empty())
    {
        // while if
        while (!st.empty() && st.top()->Edges.size() > 0)
        {
            CVertex *pHead = st.top();

            CEdge *pEOut = pHead->Edges.back();
            pEOut->bIsInGraph = false;

            if (graph.m_bIsOriented)
            {
                st.push(pEOut->pV2);

                _DelEdge(pEOut->pV2, pEOut);
            }
            else
            {
                if (pHead == pEOut->pV1)
                {
                    st.push(pEOut->pV2);

                    _DelEdge(pEOut->pV2, pEOut);
                }
                else
                {
                    st.push(pEOut->pV1);

                    _DelEdge(pEOut->pV1, pEOut);
                }
            }

            pHead->Edges.pop_back();
        }

        // while if
        while (!st.empty() && st.top()->Edges.size() == 0)
        {
            CVertex *pHead = st.top();

            EulerGraph.GetVertices().push_back(pHead);
            st.pop();

            printf("%d\n", pHead->dwID);
        }
    }
    /*
    CVertex *pLast = *EulerGraph.GetVertices().begin();
    for (CVertex *pV : EulerGraph.GetVertices())
    {
        if (pLast == pV)
            continue;

        CEdge *pEdge = new CEdge;
        pEdge->bIsInGraph = true;
        pEdge->pV1 = pLast;
        pEdge->pV2 = pV;
        pEdge->dwID = EulerGraph.GetEdges().size();

        pLast->Edges.push_back(pEdge);
        pV->Edges.push_back(pEdge);

        EulerGraph.GetEdges().push_back(pEdge);

        pLast = pV;
    }*/

    printf("\n\n\nEuler graph:\n\n");

    for (auto iEdge : EulerGraph.GetVertices())
    {
        printf("%d\n", iEdge->dwID);
    }

    /*
    for (auto iEdge : EulerGraph.GetEdges())
    {
        printf("%d %d\t \n", iEdge->pV1->dwID, iEdge->pV2->dwID);
    }*/
}
/*
void RunFleri()
{
    CGraph graph;

    E_ERROR hr;

    V_RET(graph.ParseFile("adj_mat.txt"));

    for (auto iVertex : graph.GetVertices())
    {
        iVertex->pMyData = new DWORD;
        *((DWORD *)iVertex->pMyData) = iVertex->dwID;
    }

    //graph.DFS([](int const nid) { printf("%d\n", nid); });

    CGraph EulerGraph(graph);
    EulerGraph.GetEdges().clear();
    //EulerGraph.GetVertices().clear();

    DWORD iEdge = 0;

    CVertex *pVCur = EulerGraph.GetVertices().at(rand() % EulerGraph.GetVertices().size());


    for (DWORD i = 0; i < graph.GetEdges().size(); i++)
    {
        CEdge *pBridge = nullptr;

        // по всем рёбрам
        // выбираем первое попавшееся ребро, не посещённое и не мост

        for (auto pEdge : pVCur->Edges)
        {
            // посещённое
            if (pEdge->bIsVisited)
                continue;

            // мост

            pEdge->bIsVisited = true;
            pEdge->dwID = iEdge++;

            if (EulerGraph.m_bIsOriented)
            {
                pVCur = pEdge->pV2;
            }
            else
            {
                if (pVCur == pEdge->pV1)
                    pVCur = pEdge->pV2;
                else
                    pVCur = pEdge->pV1;
            }

            DSUGet(iEdge->pV1->dwID, EulerGraph.GetVertices());
        }


        if (rand() & 1)
            *(DWORD *)V2->pMyData = *(DWORD *)V1->pMyData;
        else
            *(DWORD *)V1->pMyData = *(DWORD *)V2->pMyData;
    }

    printf("\n\n\nEuler graph:\n\n");

    for (auto iEdge : EulerGraph.GetVertices())
    {
        printf("%d\n", iEdge->dwID);
    }


    //for (auto iEdge : EulerGraph.GetEdges())
    //printf("%d %d\t \n", iEdge->pV1->dwID, iEdge->pV2->dwID);

}
*/
int main()
{
    //std::string sMask = "a?*b*c";
    //std::string sText = "apbdsadasc";

    //printf("\"%s\" by mask \"%s\": %d\n", sText.c_str(), sMask.c_str(), iswm(sMask, sText));

    //RunKruskal();
    //RunPrima();
    //RunBoruvka();

    RunRid();
    //RunFleri();

    //CGraph graph;

    //E_ERROR hr;

    //V_RET(graph.ParseFile("adj_mat.txt"));

    _getch();
    return 0;
};