Cod sursa(job #2425235)

Utilizator seba99Sebastian Balan seba99 Data 24 mai 2019 16:58:11
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> v[50002];
int grad[50002];
int sol[50002];
int n, m;

int main()
{
	int i, ii, j, x, y, ind = 1;
	f >> n >> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y;
		v[y].push_back(x);//Muchii din x care intra in y
		grad[x]++; // grad ext a lui x
	}
	for (i = 1; i <= n; i++)
	{
		if (grad[i] == 0)
		{
			sol[ind] = i; // ia fiecare frunza si o adauga la solutii
			ind++; //index de solutii
		}
	}
	for (ii = 1; ii < ind; ii++)
	{
		i = sol[ii]; // ia fiecare frunza si merge in fiecare tata
		for (j = 0; j < v[i].size(); j++)
		{
			grad[v[i][j]]--; //pt fiecare scade gradul
			if (grad[v[i][j]] == 0) //daca gradul e zero si tatal devine frunza la randul lui adauga la solutii
			{
				sol[ind] = v[i][j];
				ind++;
			}
		}
	}
	for (i = n; i >= 1; i--)
		cout << sol[i] << " ";
	return 0;
}