Cod sursa(job #1734736)

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

int noLines, noNodes;

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

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[node]->adjList.size(); i++)
	{
		int nextValue = graph[node]->adjList[i]->value;
		if (visited.find(nextValue) == visited.end())
		{
			visited.insert(nextValue);
			depth_first(nextValue);
			topologic.push(nextValue);
		}
	}
}

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

	graph.push_back(new Node(0));
	for (int i = 1; i <= noNodes; i++)
		graph.push_back(new Node(i));

	int start, end;
	for (int i = 0; i < noLines; i++)
	{
		fin >> start >> end;	
		graph[start]->adjList.push_back(graph[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();
}