Pagini recente » Cod sursa (job #726557) | Cod sursa (job #728738) | Cod sursa (job #338092) | Cod sursa (job #2759744) | Cod sursa (job #3271930)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
int n,m;
const int lmax=1e5;
int vis[lmax];
std::vector<int> G[lmax + 1];
std::vector<int> L[lmax+1];
std::vector<int> topsort;
void dfs(int x)
{
vis[x]=1;
for(auto next: L[x])
{
if(!vis[next])
dfs(next);
}
}
void dfs_topsort(int node) {
vis[node] = 1;
for(auto it : G[node]) {
if(!vis[it]) {
dfs(it);
}
}
topsort.push_back(node);
}
void sortare_topologica(int n) {
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs_topsort(i);
}
}
reverse(topsort.begin(), topsort.end());
}
int main() {
std::ifstream fin("sortaret.in");
std::ofstream fout("sortaret.out");
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
L[y].push_back(x);
}
sortare_topologica(n);
for(auto it:topsort)
fout<<it<<" ";
return 0;
}