Cod sursa(job #2798352)

Utilizator icnsrNicula Ionut icnsr Data 11 noiembrie 2021 10:46:51
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 12.1 kb
#include <bits/stdc++.h>

class Graph
{
public:
        Graph(const std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
            : nr_noduri(nr_noduri)
            , l_adiacenta(std::move(l_adiacenta))
        {
        }

        int componente_conexe() const;

        std::vector<int> distante_minime(const int start) const;

        std::vector<int> sortare_topologica() const;

        std::vector<int> grade_interne() const;

        std::vector<std::vector<int>> comp_tare_conexe() const;

        std::vector<std::vector<int>> comp_biconexe() const;

        std::vector<std::pair<int, int>> muchii_critice() const;

        static bool hakimi(std::vector<int>);

private:
        void DFS(std::vector<bool>& visited, int src) const;

        void DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                        const int src) const;

        void BFS(std::vector<int>& dists, int start) const;

        void ctc(const int src, int& idx, std::vector<int>& indexes,
                 std::vector<int>& low_link, std::vector<unsigned char>& on_stack,
                 std::stack<int>& stack, std::vector<std::vector<int>>& res) const;

        void DFS_biconexe(const int, const int, const int, std::vector<int>&,
                          std::vector<int>&, std::stack<std::pair<int, int>>&,
                          std::vector<std::vector<int>>&) const;

        void DFS_muchii_critice(const int, const int, const int, std::vector<int>&,
                                std::vector<int>&, std::stack<std::pair<int, int>>&,
                                std::vector<std::pair<int, int>>&) const;

private:
        std::size_t nr_noduri;
        std::vector<std::vector<int>> l_adiacenta;
};

int Graph::componente_conexe() const
{
        std::vector<bool> visited(nr_noduri + 1, false);

        int res = 0;
        for(int node = 1; node <= (int)nr_noduri; ++node)
        {
                if(!visited[node])
                {
                        ++res;
                        DFS(visited, node);
                }
        }

        return res;
}

std::vector<int> Graph::distante_minime(const int start) const
{
        std::vector<int> distante(nr_noduri + 1, -1);

        BFS(distante, start);

        return distante;
}

std::vector<int> Graph::sortare_topologica() const
{
        std::vector<int> sorted;

        const auto grd_i = grade_interne();
        std::vector<unsigned char> viz(nr_noduri + 1, false);

        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                if(grd_i[node] == 0 && !viz[node])
                {
                        DFS_ordine(viz, sorted, node);
                }
        }

        std::reverse(sorted.begin(), sorted.end());

        return sorted;
}

std::vector<int> Graph::grade_interne() const
{
        std::vector<int> res(nr_noduri + 1, 0);

        for(auto& l : l_adiacenta)
        {
                for(int v : l)
                {
                        ++res[v];
                }
        }

        return res;
}

void Graph::DFS(std::vector<bool>& visited, int start) const
{
        visited[start] = true;

        for(int v : l_adiacenta[start])
        {
                if(!visited[v])
                {
                        DFS(visited, v);
                }
        }
}

void Graph::DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                       const int src) const
{
        visited[src] = true;

        for(int v : l_adiacenta[src])
        {
                if(!visited[v])
                {
                        DFS_ordine(visited, res, v);
                }
        }

        res.push_back(src);
}

void Graph::BFS(std::vector<int>& dists, int start) const
{
        std::queue<int> q;
        q.push(start);
        dists[start] = 0;

        while(!q.empty())
        {
                const auto node = q.front();
                q.pop();

                for(int v : l_adiacenta[node])
                {
                        if(dists[v] == -1)
                        {
                                q.push(v);
                                dists[v] = dists[node] + 1;
                        }
                }
        }
}

bool Graph::hakimi(std::vector<int> degrees)
{
        if(degrees.empty())
        {
                return true;
        }

        while(true)
        {
                if(std::any_of(degrees.begin(), degrees.end(),
                               [](const int deg)
                               {
                                       return deg < 0;
                               }))
                {
                        return false;
                }

                std::sort(degrees.begin(), degrees.end());
                if(degrees.back() == 0)
                {
                        return true;
                }

                const int current_deg = degrees.back();
                degrees.pop_back();

                if(static_cast<std::size_t>(current_deg) > degrees.size())
                {
                        return false;
                }

                for(auto it = degrees.rbegin(); it != degrees.rbegin() + current_deg; ++it)
                {
                        --(*it);
                }
        }
}

std::vector<std::vector<int>> Graph::comp_tare_conexe() const
{
        std::vector<std::vector<int>> res;

        int idx = 0;
        std::stack<int> stack;
        std::vector<int> indexes(nr_noduri + 1, -1);
        std::vector<unsigned char> on_stack(nr_noduri + 1, false);
        std::vector<int> low_link(nr_noduri + 1);

        for(int node = 1; node <= (int)nr_noduri; ++node)
        {
                if(indexes[node] == -1)
                {
                        ctc(node, idx, indexes, low_link, on_stack, stack, res);
                }
        }

        return res;
}

void Graph::ctc(const int src, int& idx, std::vector<int>& indexes, std::vector<int>& low_link,
                std::vector<unsigned char>& on_stack, std::stack<int>& stack,
                std::vector<std::vector<int>>& res) const
{
        indexes[src] = idx;
        low_link[src] = idx;
        ++idx;

        stack.push(src);
        on_stack[src] = true;

        for(const int neigh : l_adiacenta[src])
        {
                if(indexes[neigh] == -1)
                {
                        ctc(neigh, idx, indexes, low_link, on_stack, stack, res);
                        low_link[src] = std::min(low_link[src], low_link[neigh]);
                }
                else if(on_stack[neigh])
                {
                        low_link[src] = std::min(low_link[src], indexes[neigh]);
                }
        }

        if(low_link[src] == indexes[src])
        {
                int w;
                std::vector<int> partial_res;
                do
                {
                        w = stack.top();
                        stack.pop();
                        on_stack[w] = false;
                        partial_res.push_back(w);
                } while(src != w);
                res.emplace_back(std::move(partial_res));
        }
}

std::vector<std::vector<int>> Graph::comp_biconexe() const
{
        std::vector<int> depths(nr_noduri + 1, -1);
        std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
        std::stack<std::pair<int, int>> stack_muchii;

        std::vector<std::vector<int>> res;

        DFS_biconexe(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);

        for(auto& comp : res)
        {
                std::sort(comp.begin(), comp.end());
        }

        for(auto& comp : res)
        {
                comp.resize(std::unique(comp.begin(), comp.end()) - comp.begin());
        }

        return res;
}

void Graph::DFS_biconexe(const int src, const int parent, const int current_depth,
                         std::vector<int>& depths, std::vector<int>& lowest_reachable_depth,
                         std::stack<std::pair<int, int>>& stack_muchii,
                         std::vector<std::vector<int>>& res) const
{
        depths[src] = current_depth;
        lowest_reachable_depth[src] = current_depth;

        for(const int neigh : l_adiacenta[src])
        {
                if(depths[neigh] == -1 && neigh != parent)
                {
                        stack_muchii.push(std::make_pair(src, neigh));
                        DFS_biconexe(neigh, src, current_depth + 1, depths,
                                     lowest_reachable_depth, stack_muchii, res);

                        lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
                                                               lowest_reachable_depth[neigh]);

                        if(lowest_reachable_depth[neigh] >= depths[src])
                        {
                                std::vector<int> component;

                                int muchie_x;
                                int muchie_y;
                                do
                                {
                                        muchie_x = stack_muchii.top().first;
                                        muchie_y = stack_muchii.top().second;

                                        component.push_back(muchie_x);
                                        component.push_back(muchie_y);

                                        stack_muchii.pop();
                                } while(!(muchie_x == src && muchie_y == neigh));

                                res.emplace_back(std::move(component));
                        }
                }
                else if(neigh != parent)
                {
                        lowest_reachable_depth[src] =
                            std::min(lowest_reachable_depth[src], depths[neigh]);
                }
        }
}

std::vector<std::pair<int, int>> Graph::muchii_critice() const
{
        std::vector<int> depths(nr_noduri + 1, -1);
        std::vector<int> lowest_reachable_depth(nr_noduri + 1, INT_MAX);
        std::stack<std::pair<int, int>> stack_muchii;

        std::vector<std::pair<int, int>> res;

        DFS_muchii_critice(1, 0, 0, depths, lowest_reachable_depth, stack_muchii, res);

        return res;
}

void Graph::DFS_muchii_critice(const int src, const int parent, const int current_depth,
                               std::vector<int>& depths,
                               std::vector<int>& lowest_reachable_depth,
                               std::stack<std::pair<int, int>>& stack_muchii,
                               std::vector<std::pair<int, int>>& res) const
{
        depths[src] = current_depth;
        lowest_reachable_depth[src] = current_depth;

        for(const int neigh : l_adiacenta[src])
        {
                if(depths[neigh] == -1 && neigh != parent)
                {
                        stack_muchii.push(std::make_pair(src, neigh));
                        DFS_muchii_critice(neigh, src, current_depth + 1, depths,
                                           lowest_reachable_depth, stack_muchii, res);

                        lowest_reachable_depth[src] = std::min(lowest_reachable_depth[src],
                                                               lowest_reachable_depth[neigh]);

                        if(lowest_reachable_depth[neigh] > depths[src])
                        {
                                res.emplace_back(std::make_pair(neigh, src));
                        }
                }
                else if(neigh != parent)
                {
                        lowest_reachable_depth[src] =
                            std::min(lowest_reachable_depth[src], depths[neigh]);
                }
        }
}

int main()
{
        int N, M;
        scanf("%d %d", &N, &M);

        std::vector<std::vector<int>> list(N + 1);
        for(int i = 0; i < M; ++i)
        {
                int a, b;
                scanf("%d %d", &a, &b);

                list[a].push_back(b);
        }

        const Graph g(N, std::move(list));

        const auto noduri_sortate = g.sortare_topologica();

        for(int v : noduri_sortate)
        {
                printf("%d ", v);
        }
        putchar('\n');
}

static const int redirect_io = []()
{
        std::freopen("sortaret.in", "r", stdin);
        std::freopen("sortaret.out", "w", stdout);
        return 0;
}();