Topological Sort
(graph/topological_sort.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/topological_sort.hpp"

Description

トポロジカルソートは，有向非巡回グラフ (DAG) の頂点を順序付けして，任意の辺 $(u, v)$ について $u$ が $v$ よりも前に来るように並べることである．

Operations

• vector<int> topological_sort(vector<vector<int>> G)
  • $G$ のトポロジカルソートを返す．$G$ が DAG でないならば，空のリストを返す
  • 時間計算量: $O(V + E)$

Code

#pragma once
#include <algorithm>
#include <stack>
#include <vector>

std::vector<int> topological_sort(const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<int> par_count(n);
    for (int u = 0; u < n; ++u) {
        for (int v : G[u]) ++par_count[v];
    }
    std::stack<int> st;
    for (int v = 0; v < n; ++v) {
        if (par_count[v] == 0) st.push(v);
    }

    std::vector<int> ord;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        ord.push_back(u);
        for (int v : G[u]) {
            --par_count[v];
            if (par_count[v] == 0) st.push(v);
        }
    }

    if (*std::ranges::max_element(par_count) > 0) return {};
    return ord;
}

#line 2 "graph/topological_sort.hpp"
#include <algorithm>
#include <stack>
#include <vector>

std::vector<int> topological_sort(const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    std::vector<int> par_count(n);
    for (int u = 0; u < n; ++u) {
        for (int v : G[u]) ++par_count[v];
    }
    std::stack<int> st;
    for (int v = 0; v < n; ++v) {
        if (par_count[v] == 0) st.push(v);
    }

    std::vector<int> ord;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        ord.push_back(u);
        for (int v : G[u]) {
            --par_count[v];
            if (par_count[v] == 0) st.push(v);
        }
    }

    if (*std::ranges::max_element(par_count) > 0) return {};
    return ord;
}

Back to top page