© 2020 Neveles. All rights reserved.

Graph Graph::getMetagraph()
{
    Graph rGraph(*this);

    rGraph.reverse();

    rGraph.dfs();

    vector<Vertex*> orderedV = rGraph.getVertices();

    // Сортируем вершины обратного графа по пост значениям
    getOrderByPost(orderedV);

    for (auto& v : orderedV)
    {
        vertices[v->num].visited = false;
    }

    int current_scc = -1;

    // Расставляем номера вершин метаграфа
    for (auto& v : orderedV)
    {
        if (vertices[v->num].visited == false)
        {
            this->explore(v->num);

            ++current_scc;
        }

        vertices[v->num].scc = current_scc;
    }

    vector<list<int>> metaE(current_scc + 1);

    //Составляем массив связей метаграфа
    for (auto& v : this->vertices)
    {
        for (auto& i : edges[v.num])
        {
            if (v.scc != vertices[i].scc)
            {
                if (find(metaE[v.scc].begin(), metaE[v.scc].end(), vertices[i].scc) == metaE[v.scc].end())
                {
                    metaE[v.scc].push_back(vertices[i].scc);
                }
            }
        }
    }

    return Graph(metaE);
}