Cod sursa(job #2854965)

Utilizator IanisOpritescuOpritescu Ianis IanisOpritescu Data 21 februarie 2022 21:29:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;
int Q[50005];
int gr[50005];
vector <int> G[50005];

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
		gr[y] ++;
	}

	for (int i = 1; i <= n; i++)
		if (gr[i] == 0)
			Q[++Q[0]] = i;

	for (int i = 1; i <= n; i++)
	{
		int x = Q[i];

		vector <int> ::iterator it;
		for (it = G[x].begin(); it != G[x].end(); it++)
		{
			gr[*it] --;
			if (gr[*it] == 0) Q[++Q[0]] = *it;
		}
	}

	for (int i = 1; i <= n; i++)
		fout << Q[i] << " ";
	return 0;
}