Cod sursa(job #2301541)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 13 decembrie 2018 09:21:02
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define Nmax 50005

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m, x, y;
vector <int> v[Nmax];
vector <int> ans;
bitset <Nmax> seen;

void dfs(int cn)
{
    seen[cn]=1;
    for (int i = 0, l=v[cn].size(); i < l; i++)
    {
        int nn=v[cn][i];
        if(seen[nn] == 1) continue;
        dfs(nn);
    }
    ans.push_back(cn);
}

int main()
{
    f >> n >> m;
    while(m--)
    {
        f >> x >> y;
        v[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if(seen[i] == 0)
            dfs(i);
    while(ans.size())
    {
        g << ans.back() << " ";
        ans.pop_back();
    }

    return 0;
}