Cod sursa(job #2423961)

Utilizator GashparzPredescu Eduard-Alexandru Gashparz Data 22 mai 2019 12:22:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector<int> v[500002];
int grad[500002];
int sol[5000002];
int N, M;

int main()
{
	int x, y, cnt = 1, aux;
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	fin >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		fin >> x >> y;
		v[y].push_back(x);
		grad[x]++;
	}
	for (int i = 1; i <= N; i++)
	{
		if (grad[i] == 0)
		{
			sol[cnt] = i;
			cnt++;
		}
	}
	for (int i = 1; i < cnt; i++)
	{
		aux = sol[i];
		for (int j = 0; j < v[aux].size(); j++)
		{
			grad[v[aux][j]]--;
			if (grad[v[aux][j]] == 0)
			{
				sol[cnt] = v[aux][j];
				cnt++;
			}
		}
	}
	for (int i = N; i >= 1; i--)
		fout << sol[i] << " ";
}