Cod sursa(job #340780)

Utilizator alexandru92alexandru alexandru92 Data 16 august 2009 15:43:13
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <vector>
#include <stack>
#include <set>
#define Nmax 50100
using namespace std;
ifstream in;
ofstream out;
set<int> list[Nmax];
set<int>::const_iterator it,iend;
stack<int> st;
vector<int> v;
bitset<Nmax> uz;
int main()
{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 )
	{uz.flip(i);
		if( list[i].empty() )
		{
			v.push_back(i);
		}
		else {
				st.push(i);
				while( !st.empty() )
				{
					x=st.top(); st.pop(); v.push_back(x);
					it=list[x].begin(); iend=list[x].end();
					while( it != iend )
					{
						if( !uz[*it] )
						{
							uz.flip(*it); st.push(*it);
						}
					   ++it;
					}
				}
		      }
	}
	out.open("sortaret.out");
	copy( v.begin(), v.end(), ostream_iterator<int>(out," ") );
	return 0;
}