Cod sursa(job #2398045)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 5 aprilie 2019 00:03:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<queue>
#include<vector>
#define NMAX 50005

using namespace std;

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

int main()
{
	int n, m;
	fin >> n >> m;

	vector<int>G[n+3];
	vector<int>grad(n+3,0);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		grad[b]++;
	}

	queue<int>q;

	for (int i = 1; i <= n; i++)
	{
		if (grad[i] == 0)
		{
			q.push(i);
		}
	}

	vector<int>ans;

	while (q.size())
	{
		int nod = q.front();
		q.pop();
		ans.push_back(nod);

		for (unsigned int i = 0; i < G[nod].size(); i++)
		{
			grad[G[nod][i]]--;
			if (grad[G[nod][i]] == 0)
			{
				q.push(G[nod][i]);
			}
		}
	}

	for (unsigned int i = 0; i < ans.size(); i++)
	{
		fout << ans[i] << " ";
	}

	
	fin.close();
	fout.close();
	return 0;
}