Cod sursa(job #2199458)

Utilizator adriangh3Adrian Gheorghiu adriangh3 Data 27 aprilie 2018 20:02:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
#define MAXIM 50001
vector <int> v[MAXIM];
int coada[MAXIM], deg[MAXIM];

int main()
{
	int n, m, a, b, u=-1, p=0;
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		in >> a >> b;
		v[a].push_back(b);
		deg[b]++;
	}
	for (int i = 1; i <= n; i++) if (deg[i] == 0) coada[++u] = i;
	while (p <= u)
	{
		int x = coada[p], length=v[x].size();
		p++;
		for (int i = 0; i < length; i++)
		{
			deg[v[x][i]]--;
			if (deg[v[x][i]] == 0) coada[++u] = v[x][i];
		}
	}
	for (int i = 0; i < n; i++) out << coada[i] << ' ';
	return 0;
}