graph/topological_sort.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "graph/topological_sort.hpp"

Verified with

• verify/yosupo_graph/graph_scc.test.cpp

Code

#ifndef KK2_GRAPH_TOPOLOGICAL_SORT_HPP
#define KK2_GRAPH_TOPOLOGICAL_SORT_HPP 1

#include <queue>
#include <vector>

namespace kk2 {

template <class G> std::vector<int> topological_sort(const G &graph) {
    int siz = size(graph);
    std::vector<int> indegree(siz);
    for (int i = 0; i < siz; i++)
        for (int j : graph[i]) indegree[j]++;
    std::vector<int> res;
    std::queue<int> que;
    for (int i = 0; i < siz; i++)
        if (indegree[i] == 0) que.push(i);
    while (!que.empty()) {
        int ver = que.front();
        que.pop();
        res.push_back(ver);
        for (int i : graph[ver]) {
            indegree[i]--;
            if (indegree[i] == 0) que.push(i);
        }
    }
    return res;
}

} // namespace kk2

#endif // KK2_GRAPH_TOPOLOGICAL_SORT_HPP

#line 1 "graph/topological_sort.hpp"



#include <queue>
#include <vector>

namespace kk2 {

template <class G> std::vector<int> topological_sort(const G &graph) {
    int siz = size(graph);
    std::vector<int> indegree(siz);
    for (int i = 0; i < siz; i++)
        for (int j : graph[i]) indegree[j]++;
    std::vector<int> res;
    std::queue<int> que;
    for (int i = 0; i < siz; i++)
        if (indegree[i] == 0) que.push(i);
    while (!que.empty()) {
        int ver = que.front();
        que.pop();
        res.push_back(ver);
        for (int i : graph[ver]) {
            indegree[i]--;
            if (indegree[i] == 0) que.push(i);
        }
    }
    return res;
}

} // namespace kk2

Back to top page