Cod sursa(job #373133)

Utilizator alexandru92alexandru alexandru92 Data 12 decembrie 2009 19:01:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on December 12, 2009, 11:32 AM
 */
#include <stack>
#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, grad;
bool *mark;
inline void DFS( int x )
{vector<int>::const_iterator it=M[x].begin(), iend=M[x].end();
    mark[x]=true; //mark a visited
    for( ; it < iend;  ++it )
        if( !mark[*it] )
            DFS(*it);
    sol.pb(x);
} 
void solve( int n )
{vector<int>::const_iterator start, ending;
    for( int i=0; i < n; ++i )
    {
        for( start=M[sol[i]].begin(), ending=M[sol[i]].end(); start < ending; ++start )
        {
             --grad[*start];
             if( 0 == grad[*start] )
                sol.pb(*start);
        }       
    }
}
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);
    grad.resize(n+1);
    while( m-- )
    {
        in>>x>>y;
        ++grad[y];
        M[x].pb(y);
    }/*
    for( i=1; i <= n; ++i )
       if( !mark[i] )
          DFS(i);*/
    for( i=1; i <= n; ++i )
        if( 0 == grad[i] )
            sol.pb(i);
    solve(n);
    ofstream out(OutFile);
    copy( sol.begin(), sol.end(), ostream_iterator<int>(out, " ") );
    free(mark);
    return (EXIT_SUCCESS);
}