Cod sursa(job #1876517)

Utilizator loghin.alexandruLoghin Alexandru loghin.alexandru Data 12 februarie 2017 14:01:09
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <vector>
#include <list>
#include <fstream>

using namespace std;


ifstream fin("sortaret.in");
ofstream fout("sortaret.out");




vector<list<int>> nodes;

vector<bool> used;

list<int> output;

void DFS(int nod)
{
	used[nod] = true;
	for (auto it = nodes[nod].begin(); it != nodes[nod].end(); ++it)
	{
		if (used[*it] == false)
		{
			DFS(*it);
		}
	}
	output.push_back(nod);
}


void topologicSort(int nodMax)
{
	for (auto i = 1; i <= nodMax; ++i)
	{
		if (used[i] == false)
		{
			DFS(i);
		}
	}
}


int main()
{
	int nodMax, link;
	fin >> nodMax >> link;
	nodes.resize(nodMax + 1);
	used.resize(nodMax + 1);
	for (auto i = 0; i < link; ++i)
	{
		int x, y;
		fin >> x >> y;
		nodes[x].push_back(y);
	}
	topologicSort(1);
	for (auto x : output)
	{
		fout << x << ' ';
	}
	return 0;
}