Cod sursa(job #2210907)

Utilizator AlexDabuDabu Alexandru AlexDabu Data 8 iunie 2018 16:09:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

#define MAXN 50005

using namespace std;

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

int N, M;
vector <int> adjList[MAXN];
vector <int> L;
int indegree[MAXN] = { 0 };

void Read(void)
{
	int x, y;
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y;
		indegree[y]++;
		adjList[x].push_back(y);
	}
}

void Sortare(void)
{
	int n;

	vector <int> S;
	for (int i = 1; i <= N; i++)
	{
		if (!indegree[i])
		{
			S.push_back(i);
		}
	}
	while (!S.empty())
	{
		n = S.back();
		S.pop_back();

		L.push_back(n);
		for (int m : adjList[n])
		{
			indegree[m]--;
			if (!indegree[m])
				S.push_back(m);
		}
	}
}

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

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