Mai intai trebuie sa te autentifici.
Cod sursa(job #2912247)
Utilizator | Data | 7 iulie 2022 16:32:10 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.08 kb |
#include<fstream>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
ofstream cout("sortaret.out");
ifstream cin("sortaret.in");
vector<vector<int>> v;
vector<int> toposort;
vector<bool> check(300001);
void dfs(int node)
{
check[node] = 1;
for(auto x : v[node])
{
if(!check[x])
{
dfs(x);
}
}
toposort.push_back(node);
}
void solve()
{
int n, m; cin >> n >> m;
v = vector<vector<int>> (n+1);
for(int z = 0; z < m; z++)
{
int a, b; cin >> a >> b;
v[a].push_back(b);
}
for(int z = 1; z <= n; z++)
{
if(!check[z])
{
dfs(z);
}
}
for(vector<int>::reverse_iterator it = toposort.rbegin(); it != toposort.rend(); it++)
{
cout << *it << ' ';
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
//int tt;
///cin >> tt;
//while(tt--)
//{
solve();
//}
}