Cod sursa(job #730322)

Utilizator rayvianPricope Razvan rayvian Data 6 aprilie 2012 07:57:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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=1; i<=noduri; i++)
  {
    graph.push_back(new Node(i));
    gasit[i]=graph[graph.size()-1];
  }

	for(int i=0; i<muchii; i++)
	{
		int start,end;
		fin>>start>>end;
		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;
}