Cod sursa(job #2479127)

Utilizator XsoundCristian-Ioan Roman Xsound Data 23 octombrie 2019 12:05:42
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#define Nmax 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

bitset < Nmax > b;
vector < int > v[Nmax];
stack  < int > s;

int n,m;

void citire();
void afisare();

void Dfs(int x);

int main()
{
    citire();

    for ( int i = 1; i<=n; i++ )
        if ( b[i] == 0 )
            Dfs(i);

    afisare();
}

void Dfs(int x)
{
    int lg = v[x].size();

    for ( int i = 0; i < lg; i++ )
    {
        if ( b[v[x][i]] == 0 )
            Dfs(v[x][i]);
    }

    s.push(x);
    b[x] = 1;
    return;
}

void afisare()
{
    while ( !s.empty() )
    {
        fout << s.top() <<' ';
        s.pop();
    }
}

void citire()
{
    int x,y;

    fin >> n >> m;

    for ( int i = 0 ; i <= m; i++ )
    {
        fin >> x >> y;

        v[x].push_back(y);
    }
}