Cod sursa(job #2515890)

Utilizator HaripAl3xHarip Alexandru HaripAl3x Data 29 decembrie 2019 18:30:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
#define NM 50001

using namespace std;

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

void read();

int N, M,gint[NM],Q[NM];
vector <int> G[NM];

int main()
{
	read();
	vector <int>::iterator it;
	int lg = 0, x;
	for (int i = 1; i <= N; i++)
		if (gint[i] == 0)
			Q[++lg] = i;
	for (int i = 1; i <= N; i++)
	{
		x = Q[i];
		for (it = G[x].begin(); it != G[x].end(); it++)
		{
			gint[*it]--;
			if (gint[*it] == 0)
				Q[++lg] = *it;
		}
	}
	for (int i = 1; i <= N; i++)
		fout << Q[i] << ' ';
	fout << '\n';
}


void read()
{
	int x, y;
	fin >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		fin >> x >> y;
		G[x].push_back(y);
		gint[y]++;
	}
}