Cod sursa(job #1384310)

Utilizator OrolesVultur Oroles Data 11 martie 2015 00:09:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

static const int WHITE = 0;
static const int GREY = 1;
static const int BLACK = 2;

vector<vector<int> > edges(50001);
vector<int> colors(50001,WHITE);
list<int> rez;

void visit(int n)
{
	colors[n] = GREY;
	for( int i = 0; i < edges[n].size(); ++i )
	{
		if ( colors[edges[n][i]] == WHITE )
		{
			visit(edges[n][i]);
		}
	}
	colors[n] = BLACK;
	rez.push_front( n );
}

void sort_top(int N)
{
	for ( int i = 1; i <= N; ++i )
	{
		if ( colors[i] == WHITE )
		{
			visit(i);
		}
	}
}

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

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