Mai intai trebuie sa te autentifici.
Cod sursa(job #2530743)
Utilizator | Data | 25 ianuarie 2020 11:26:42 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.7 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in;
ofstream out;
vector<set<int>> edge;
int n,m,visited[50005];
stack<int> sorted;
void DFS(int st)
{
visited[st]=1;
for(auto& it:edge[st])
{
if(!visited[it])
DFS(it);
}
sorted.push(st);
}
void top_sort()
{
for(int i=1;i<=n;i++)
if(!visited[i])
DFS(i);
}
int main()
{
in.open("sortaret.in");
out.open("sortaret.out");
in>>n>>m;
edge.resize(n+2);
for(int i=1;i<=m;i++)
{
int x,y;
in>>x>>y;
edge[x].insert(y);
}
top_sort();
while (!sorted.empty()) {
out<<sorted.top()<<" ";
sorted.pop();
}
return 0;
}