Cod sursa(job #341069)

Utilizator alexandru92alexandru alexandru92 Data 17 august 2009 14:12:58
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <bitset>
#include <stack>
#include <set>
#define Nmax 111
using namespace std;
ifstream in;
ofstream out;
struct Order
{
	inline bool operator() ( int a, int b )
	{
		return a > b;
	}
};
set<int, Order> list[Nmax];
stack<int> s;
bitset<Nmax> uz;
void DFS( int v )
{set<int,Order>::const_iterator it,iend;
    uz.flip(v);
    for( iend=list[v].end(),it=list[v].begin(); it != iend; ++it )
       if( !uz[*it] )
          DFS(*it);
    s.push(v);
}
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);
    }
    for( i=1; i<=N; ++i )
       if( !uz[i] )
       {
           if( list[i].empty() )
           {
               s.push(i);
           }
           else DFS( i );
       }
    out.open("sortaret.out");
    while( !s.empty() ) out<<s.top()<<' ',s.pop();
    return 0;
}