Cod sursa(job #2313641)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 7 ianuarie 2019 11:48:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define N 50005

using namespace std;

ifstream fin( "sortaret.in" );
ofstream fout( "sortaret.out" );

vector <int> G[N];
int n, m;
bool viz[N];
stack <int> S;

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

void DFS( int x )
{
    int i;
    viz[x] = 1;
    for ( i = 0; i < G[x].size(); ++i )
         if ( !viz[G[x][i]] )
             DFS(G[x][i]);
    S.push(x);
}

void SortareTopologica()
{
    int i;
    for ( i = 1; i <= n; ++i )
         if ( !viz[i] )
             DFS(i);
    while ( !S.empty() )
           { fout << S.top() << ' ';
             S.pop();
           }
}

int main()
{   read();
    SortareTopologica();
    fout.close();
    return 0;
}