src/graph/topological_sort.hpp

View this file on GitHub
Last update: 2025-12-29 18:40:11+09:00
Include: #include "src/graph/topological_sort.hpp"

Depends on

src/template.hpp

Code

#pragma once
#include "../template.hpp"

inline 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(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/graph/topological_sort.hpp"

inline 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;
}