Topological Sort
(lib/graph/topological_sort.hpp)

• View this file on GitHub
• Last update: 2024-11-25 23:10:43+09:00
• Include: #include "lib/graph/topological_sort.hpp"

Topological Sort

概要

トポロジカルソートで辞書順最小のものを求めます。

計算量

頂点数を $V$、辺の数を $E$ とすると、$\mathrm{O}(E + V \log V)$

Required by

• lib/graph/reachable_query.hpp

Code

#pragma once

/**
 * @brief Topological Sort
 * @docs docs/graph/topological_sort.md
 */

#include <vector>
#include <queue>

template <typename T>
std::vector<T> topological_sort(const std::vector<std::vector<T>> &G){
    int siz = (int) G.size();
    std::vector<int> indegree(siz);
    for(int i = 0; i < siz; i++){
        for(auto x : G[i]){
            indegree[x]++;
        }
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for(int i = 0; i < siz; i++){
        if(indegree[i] == 0){
            heap.push(i);
        }
    }

    std::vector<T> res;
    while(!heap.empty()){
        int node = heap.top();
        heap.pop();
        res.push_back(node);
        for(auto x : G[node]){
            indegree[x]--;
            if(indegree[x] == 0){
                heap.push(x);
            }
        }
    }
    return res;
}

#line 2 "lib/graph/topological_sort.hpp"

/**
 * @brief Topological Sort
 * @docs docs/graph/topological_sort.md
 */

#include <vector>
#include <queue>

template <typename T>
std::vector<T> topological_sort(const std::vector<std::vector<T>> &G){
    int siz = (int) G.size();
    std::vector<int> indegree(siz);
    for(int i = 0; i < siz; i++){
        for(auto x : G[i]){
            indegree[x]++;
        }
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for(int i = 0; i < siz; i++){
        if(indegree[i] == 0){
            heap.push(i);
        }
    }

    std::vector<T> res;
    while(!heap.empty()){
        int node = heap.top();
        heap.pop();
        res.push_back(node);
        for(auto x : G[node]){
            indegree[x]--;
            if(indegree[x] == 0){
                heap.push(x);
            }
        }
    }
    return res;
}

Back to top page