This documentation is automatically generated by competitive-verifier/competitive-verifier
グラフの隣接リストを元に,各辺について終点より始点が先にくる頂点配列を求める.
topological(lst)
:隣接リスト lst
を元に,トポロジカルソートした頂点配列を返す.topological(lst, indeg)
:隣接リスト lst
,頂点の入次数を格納した配列 indeg
を元に,トポロジカルソートした頂点配列を返す.頂点数を $V$,辺の数を $E$ とする.
topological(lst)
:$O(V+E)$topological(lst, indeg)
:$O(V+E)$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#include "../structure/2d_array.cpp"
vector<int> topological(v2d<int> &lst, vector<int> &indeg) {
int V = lst.size(), vtmp = lst.size();
vector<int> res;
queue<int> q;
for(int i = 0; i < V; i++) {
if(indeg[i] == 0) q.push(i);
}
while(!q.empty()) {
int v = q.front();
q.pop();
for(const int nv : lst[v]) {
indeg[nv]--;
if(indeg[nv] == 0) q.push(nv);
}
res.emplace_back(v);
vtmp--;
}
if(vtmp) return {-1};
return res;
}
vector<int> topological(v2d<int> &lst) {
vector<int> indeg(lst.size(), 0);
for(int i = 0; i < lst.size(); i++)
for(const int v : lst[i]) indeg[v]++;
return topological(lst, indeg);
}
#line 2 "graph/topological_sort.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#line 2 "structure/2d_array.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct v2d {
private:
vector<vector<T>> m;
public:
v2d() {}
v2d(int h, int w) : m(h, vector<T>(w)) {}
v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
void assign(int h, int w) {
m.assign(h, vector<T>(w));
}
void assign(int h, int w, const T init) {
m.assign(h, vector<T>(w, init));
}
inline int size() const {
return m.size();
}
void in() {
for(vector<T> &v : m)
for(T &val : v) cin >> val;
}
void in(int h, int w) {
m.resize(h, vector<T>(w));
in();
}
void out() {
int h = m.size();
for(vector<T> &v : m) {
int sz = v.size();
for(int j = 0; j < sz; j++) {
cout << v[j] << (j == sz - 1 ? '\n' : ' ');
}
}
cout << flush;
}
inline vector<T> &operator[](int idx) {
assert(0 <= idx && idx < m.size());
return m[idx];
}
bool rangeout(int x, int y) {
if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
return false;
}
};
#line 10 "graph/topological_sort.cpp"
vector<int> topological(v2d<int> &lst, vector<int> &indeg) {
int V = lst.size(), vtmp = lst.size();
vector<int> res;
queue<int> q;
for(int i = 0; i < V; i++) {
if(indeg[i] == 0) q.push(i);
}
while(!q.empty()) {
int v = q.front();
q.pop();
for(const int nv : lst[v]) {
indeg[nv]--;
if(indeg[nv] == 0) q.push(nv);
}
res.emplace_back(v);
vtmp--;
}
if(vtmp) return {-1};
return res;
}
vector<int> topological(v2d<int> &lst) {
vector<int> indeg(lst.size(), 0);
for(int i = 0; i < lst.size(); i++)
for(const int v : lst[i]) indeg[v]++;
return topological(lst, indeg);
}