Cod sursa(job #2678290)

Utilizator CalinusCalin Navadaru Calinus Data 28 noiembrie 2020 11:40:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
///sortare topologica dfs

#include <bits/stdc++.h>



using namespace std;



ifstream fin("sortaret.in");

ofstream fout("sortaret.out");



vector<int> nodes[100005];

stack <int> s;

bool vizitate[100005];

int n,m;

void read()
{
    int x,y;
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>x>>y;
        nodes[x].push_back(y);
    }
}

void dfs(int node)
{
    vizitate[node] = true;
    for (auto it : nodes[node])
        if(!vizitate[it])
            dfs(it);
    s.push(node);
}

void solve()
{
    for (int i = 1; i <= n; ++i)
        if(!vizitate[i])
            dfs(i);
}

void print()
{
    while(!s.empty())
    {
        fout<<s.top()<<" ";
        s.pop();
    }
}

int main()
{
    read();
    solve();
    print();
    return 0;

}