This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#include "graph/topological_sort.hpp"
#pragma once #include <queue> std::vector<int> topological_sort(const std::vector<std::vector<int>> &g) { int n = g.size(); std::vector<int> deg(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { deg[j]++; } } std::vector<int> ret; std::queue<int> q; for (int i = 0; i < n; i++) { if (deg[i] == 0) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); ret.push_back(u); for (int v : g[u]) { if (--deg[v] == 0) { q.push(v); } } } if (int(ret.size()) != n) { return {}; } return ret; }
#line 2 "graph/topological_sort.hpp" #include <queue> std::vector<int> topological_sort(const std::vector<std::vector<int>> &g) { int n = g.size(); std::vector<int> deg(n); for (int i = 0; i < n; i++) { for (int j : g[i]) { deg[j]++; } } std::vector<int> ret; std::queue<int> q; for (int i = 0; i < n; i++) { if (deg[i] == 0) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); ret.push_back(u); for (int v : g[u]) { if (--deg[v] == 0) { q.push(v); } } } if (int(ret.size()) != n) { return {}; } return ret; }