Cod sursa(job #2458894)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 21 septembrie 2019 19:12:10
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> v[50001];
queue <int> q;
int gr[50001];
int noduri, m;

void read()
{
	f >> noduri >> m;
	int x, y;
	for (int i = 1; i <= m; i++)
	{
		f >> x >> y;
		v[x].push_back(y);
		gr[y]++;
	}

}

void solve()
{
	int i,n,node;
	int cont = 0;
	for (i = 1; i <= noduri; i++)
	{
		if (gr[i] == 0) q.push(i);
	}
	while (!q.empty())
	{
		cont++;
		node = q.front();
		n = v[node].size();
		g << node << " ";
		q.pop();
		for (i = 0; i < n; i++)
		{
			gr[v[node][i]]--;
			if (gr[v[node][i]] == 0) q.push(v[node][i]);

		}


	}

}


int main()
{

	read();
	solve();

	return 0;

}