Cod sursa(job #341013)

Utilizator alexandru92alexandru alexandru92 Data 17 august 2009 12:36:20
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <algorithm>
#include <iterator>
#include <set>
#include <vector>
#define Nmax 111
using namespace std;
ifstream in;
ofstream out;
set<int> list[Nmax];
vector<int> s;
set<int>::const_iterator it,iend;
int G[Nmax];
int main()
{register int N,M,x,y,i;
    in.open("sortaret.in");
    in>>N>>M;
    while( M-- )
    {
        in>>x>>y;
        list[x].insert(y);
        ++G[y];
    }
    for( i=1; i<=N; ++i )
       if( !G[i] ) s.push_back(i);
    out.open("sortaret.out");
    for( i=0; i < N; ++i )
       {
           for( iend=list[s[i]].end(),it=list[s[i]].begin(); it != iend; ++it )
              {
                  --G[*it];
                  if( !G[*it] ) s.push_back(*it);
              }
       }
    copy( s.begin(), s.end(), ostream_iterator<int>(out," ") );
    return 0;
}