src/topological_sort.hpp

View this file on GitHub
Last update: 2025-10-08 00:44:44+09:00
Include: #include "src/topological_sort.hpp"

Depends on

src/template.hpp

Code

#pragma once
#include "template.hpp"
vector<int> topological_sort(vector<vector<int>> g){
    vector<int> in(si(g)),ret;
    for(auto &&v: g) for(auto&& e: v) in[e]++;
    queue<int> q;
    rep(i,si(g)) if(in[i]==0) q.push(i);
    while(!q.empty()){
        int p = q.front();
        q.pop();
        ret.push_back(p);
        for(int u:g[p]) if(--in[u]==0) q.push(u);
    }
    return ret;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/topological_sort.hpp"
vector<int> topological_sort(vector<vector<int>> g){
    vector<int> in(si(g)),ret;
    for(auto &&v: g) for(auto&& e: v) in[e]++;
    queue<int> q;
    rep(i,si(g)) if(in[i]==0) q.push(i);
    while(!q.empty()){
        int p = q.front();
        q.pop();
        ret.push_back(p);
        for(int u:g[p]) if(--in[u]==0) q.push(u);
    }
    return ret;
}