Cod sursa(job #1575484)

Utilizator narcischitescuNarcis Chitescu narcischitescu Data 21 ianuarie 2016 16:06:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAX 50001

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

int n , m , x , y;
vector < int > G[MAX];
bool used[MAX];
int r[MAX] , nr ;

void dfs( int i )
{
    used[i] = true;
    for ( vector < int > ::iterator j = G[i].begin() ; j != G[i].end(); j++ )
        if ( ! used[(*j) ] )
            dfs ( (*j) );
    r[++nr] = i;
}

int main()
{
    f >> n >> m;
    for ( ;m-- ; )
    {
        f >> x >> y;
        G[x].push_back(y);
    }
    for (int i = 1 ; i <=n ; ++i )
         if  ( !used[i] )
            dfs(i);
    for ( ; nr > 0 ; nr-- )
        g << r[nr] << " " ;



    return 0;
}