Cod sursa(job #1734739)

Utilizator tavy14tIlie Octavian tavy14t Data 28 iulie 2016 02:04:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <set>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

int noLines, noNodes;

class Node
{
public:
	int value;
	vector<Node*>* adjList;
	Node(int value) { this->value = value; adjList = NULL; }
};

set<int> visited;
stack<int> topologic;
vector<Node*>* graph;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void depth_first(int node)
{
	for (int i = 0; i < graph->at(node)->adjList->size(); i++)
	{
		int nextValue = graph->at(node)->adjList->at(i)->value;
		if (visited.find(nextValue) == visited.end())
		{
			visited.insert(nextValue);
			depth_first(nextValue);
			topologic.push(nextValue);
		}
	}
}

int main()
{
	fin >> noNodes >> noLines;

	graph = new vector<Node*>(noNodes+1);
	graph->at(0) = new Node(-1);

	for (int i = 1; i <= noNodes; i++)
	{
		graph->at(i) = new Node(i);
		graph->at(i)->adjList = new vector<Node*>();
	}

	int start, end;
	for (int i = 0; i < noLines; i++)
	{
		fin >> start >> end;	
		graph->at(start)->adjList->push_back(graph->at(end));
	}

	while(topologic.size() < noNodes)
	{
		for (int i = 1; i <= noNodes; i++)
			if(visited.find(i) == visited.end())
			{
				visited.insert(i);
				depth_first(i);
				topologic.push(i);
			}
	}

	while(topologic.size() > 0)
	{
		fout << topologic.top() << ' ';
		topologic.pop();
	}

	//cin.get();
	//cin.get();
}