Cod sursa(job #729845)

Utilizator rayvianPricope Razvan rayvian Data 30 martie 2012 13:08:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <list>
using namespace std;
enum Color{
	WHITE,
	GRAY,
	BLACK
};
class Node
{
public:
	Color color;
	int val;
	vector<Node*> neigh;
	Node(int v):val(v)
	{
		color=WHITE;
	}
};
typedef vector<Node*> Graph;
int noduri;

Graph graph;

void citire()
{
	map<int,Node*> gasit;
	ifstream fin("sortaret.in");
	int muchii;
	fin>>noduri>>muchii;
	for(int i=0; i<muchii; i++)
	{
		int start,end;
		fin>>start>>end;
		if(gasit.find(start)==gasit.end())
		{
			graph.push_back(new Node(start));
			gasit[start]=graph[graph.size()-1];
		}
		if(gasit.find(end)==gasit.end())
		{
			graph.push_back(new Node(end));
			gasit[end]=graph[graph.size()-1];
		}
		gasit[start]->neigh.push_back(gasit[end]);
	}
}

list<Node *> nodes;
void dfs(Node *n)
{
	if(n->color==BLACK)
		return ;
	n->color=GRAY;
	for(int i=0; i<n->neigh.size(); i++)
		dfs(n->neigh[i]);
	n->color=BLACK;
	nodes.push_front(n);
}
void start()
{
	ofstream out("sortaret.out");
	for(int i=0; i<graph.size(); i++)
		if(graph[i]->color==WHITE)
			dfs(graph[i]);
	list<Node *>::iterator it;
	for(it=nodes.begin(); it!=nodes.end(); it++)
	{
		out<<(*it)->val<<" ";
	}
}


int main()
{
	citire();
	start();
	return 0;
}