Cod sursa(job #341120)

Utilizator alexandru92alexandru alexandru92 Data 17 august 2009 16:16:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <algorithm>
#include <iterator>
#include <stack>
#include <list>
#define Nmax 50111
using namespace std;
ifstream in;
ofstream out;
list<int> l[Nmax];
list<int> v;
list<int>::const_iterator it,iend,it2;
stack<int> st;
int G[Nmax];
int main()
{register int N,M,x,y,i;
    in.open("sortaret.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y;
        l[x].push_back(y);
        ++G[y];
    }
    for( i=1; i<=N; ++i )
       if( !G[i] ) v.push_back(i);
    for( iend=v.end(),it=v.begin(); it != iend; ++it )
    {
        for( iend=l[*it].end(),it2=l[*it].begin(); it2 != iend; ++it2 )
        {
            --G[*it2];
            if( !G[*it2] ) v.push_back(*it2);
        }
        iend=v.end();
    }
    out.open("sortaret.out");
    copy( v.begin(), v.end(), ostream_iterator<int>(out," ") );
    return 0;
}