Cod sursa(job #372950)

Utilizator alexandru92alexandru alexandru92 Data 12 decembrie 2009 11:53:13
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 12, 2009, 11:32 AM
 */
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
#define InFile "sortaret.in"
#define OutFile "sortaret.out"
#define pb push_back


/*
 * 
 */
using namespace std;
vector< vector<int> > M;
vector< int > sol;
vector<int>::const_iterator it, iend;
bool *mark;
inline void DFS( int x )
{
    mark[x]=true; //mark a visited
    for( it=M[x].begin(), iend=M[x].end(); it < iend;  ++it )
        if( !mark[*it] )
            DFS(*it);
    sol.pb(x);
}
int main(int argc, char** argv)
{int n, m, x, y, i;
    ifstream in(InFile);
    in>>n>>m;
    mark=(bool*)calloc( n+1, sizeof(bool) );
    M.resize(n+1);
    while( m-- )
    {
        in>>x>>y;
        M[x].pb(y);
    }
    for( i=1; i <= n; ++i )
       if( !mark[i] )
          DFS(i);
    ofstream out(OutFile);
    copy( sol.begin(), sol.end(), ostream_iterator<int>(out, " ") );
    free(mark);
    return (EXIT_SUCCESS);
}