Cod sursa(job #1384272)

Utilizator OrolesVultur Oroles Data 10 martie 2015 23:47:07
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int,int> > edges;
list<int> rez;
vector<int> temp;
vector<int> mark;

bool visit(int n)
{
	if ( find(temp.begin(), temp.end(), n ) != temp.end() )
	{
		return false;
	}
	if ( find(mark.begin(), mark.end(), n ) == mark.end() )
	{
		temp.push_back( n );
		for( vector<pair<int,int> >::iterator it = edges.begin(); it != edges.end(); ++it )
		{
			if ( it->first == n )
			{
				visit(it->second);
			}
		}
		mark.push_back( n );
		temp.erase( remove( temp.begin(), temp.end(), n ), temp.end() );
		rez.push_front( n );
	}
	return true;
}

void sort_top(int N)
{
	for ( int i = 1; i <= N; ++i )
	{
		if ( !visit(i) )
		{
			rez.clear();
			temp.clear();
			mark.clear();
		}
	}
}

int main( int argc, char* argv[] )
{
	ifstream inputFile ("sortaret.in");
	ofstream outputFile ("sortaret.out");
	edges.reserve(200000);
	temp.reserve(100000);
	mark.reserve(100000);
	int N, M;
	inputFile >> N >> M;
	for ( int i = 0; i < M; ++i )
	{
		int first, second;
		inputFile >> first >> second;
		edges.push_back( pair<int,int>( first,second ) ); 
	}
	sort_top(N);
	for ( list<int>::iterator it = rez.begin(); it != rez.end(); ++it )
	{
		outputFile << *it << " ";
	}

	inputFile.close();
	outputFile.close();
	return 0;
}