Pagini recente » Cod sursa (job #2445473) | Cod sursa (job #1270969) | Cod sursa (job #1142243) | Cod sursa (job #3221755) | Cod sursa (job #883260)
Cod sursa(job #883260)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct vertex {
vertex() { ninedge=0; sort=false; }
int ninedge;
vector<int> outedge;
bool sort;
};
vector<vertex> graph;
vector<int> toposort;
void dfs(vertex &v, int ind) {
if (v.ninedge!=0) return;
toposort.push_back(ind);
v.sort=true;
for (int j=0; j<int(v.outedge.size()); ++j) {
--graph[v.outedge[j]].ninedge;
dfs(graph[v.outedge[j]],v.outedge[j]);
}
}
int main() {
ifstream fin("test1.in");
ofstream fout("sortaret.out");
int n, nedge;
fin >> n >> nedge;
graph.resize(n+1);
for (int i=0,from,to; i<nedge; ++i) {
fin >> from >> to;
graph[from].outedge.push_back(to);
++graph[to].ninedge;
}
for (int i=1; i<=n; ++i) {
if (graph[i].sort || graph[i].ninedge!=0) continue;
dfs(graph[i],i);
}
for (int i=0; i<n; ++i) fout << toposort[i] << ' ';
return 0;
}