Cod sursa(job #340788)

Utilizator alexandru92alexandru alexandru92 Data 16 august 2009 15:56:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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 )
	   if( !uz[i] )
	   {uz.flip(i);
            if( list[i].empty() )
            {
                v.push_back(i);
            }
            else {v.push_back(i);
                    st.push(i);
                    while( !st.empty() )
                    {
                        x=st.top(); st.pop();
                        it=list[x].begin(); iend=list[x].end();
                        while( it != iend )
                        {
                            if( !uz[*it] )
                            {
                                uz.flip(*it); st.push(*it); v.push_back(*it);
                            }
                            ++it;
                        }
                    }
                }
	  }
	out.open("sortaret.out");
	copy( v.begin(), v.end(), ostream_iterator<int>(out," ") );
	return 0;
}