Pagini recente » Cod sursa (job #189585) | Cod sursa (job #99362) | Cod sursa (job #31807) | Cod sursa (job #821983) | Cod sursa (job #1449556)
#include <stack>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
template <typename T>
using bag = stack<T, vector<T>>;
vector<int> toposort(const vector<vector<int>>& graf){
vector<int> ret, in_deg(graf.size(), 0);
for(const auto& x : graf){
for(const auto y : x){
++in_deg[y]; } }
bag<int> de_viz;
for(int i = 0; i < graf.size(); ++i){
if(in_deg[i] == 0){
de_viz.push(i); } }
for(int cur ; ret.size() < graf.size(); ){
cur = de_viz.top();
de_viz.pop();
ret.push_back(cur);
for(const auto next : graf[cur]){
--in_deg[next];
if(!in_deg[next]){
de_viz.push(next); } } }
return ret; }
vector<vector<int>> citeste_graf(ifstream& f){
vector<vector<int>> graf;
int n, m;
f >> n >> m;
graf.resize(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
graf[a-1].push_back(b-1); }
return graf; }
int main(){
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const auto& sortare = toposort(citeste_graf(f));
for(const auto x : sortare){
g << (x+1) << ' ' ; }
return 0; }