Cod sursa(job #2210889)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 8 iunie 2018 15:44:08
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
vector <int> graph[50000];
vector <int> S , L;
int indegree[50000] = { 0 };

void Read(void)
{
	pair <int, int> prop;
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> prop.first >> prop.second;
		indegree[prop.second]++;
		graph[prop.first].push_back(prop.second);
	}
	for (int i = 0; i < N; i++)
	{
		if (!indegree[i])
		{
			S.push_back(i);
		}
	}
}

void Sortare(void)
{
	while (!S.empty())
	{
		L.push_back(S.back());
		S.pop_back();
		for (unsigned int i = 0; i < graph[L.at(L.size() - 1)].size(); i++)
		{
			indegree[graph[L.at(L.size() - 1)].at(i)]--;
			if (!indegree[graph[L.at(L.size() - 1)].at(i)])
			{
				S.push_back(graph[L.at(L.size() - 1)].at(i));
			}
		}
	}
}

void Print(void)
{
	for (int i = 0; i < L.size() - 1; i++)
	{
		fout << L.at(i) << ' ';
	}
}

int main(void)
{
	Read();
	Sortare();
	Print();
	return 0;
}