Cod sursa(job #2423181)

Utilizator toni123Mititelu George-Antonio toni123 Data 20 mai 2019 21:34:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

int main()
{
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");

	int n, m, x, y, i;

	in >> n >> m;


	vector<vector<int>> Graf(n);
	vector<int> grad(n+1, 0);
	vector<int> ordonate;
	queue<int> C;

	for(i=0; i<m; ++i)
	{
		in >> x >> y;
		x--;
		y--;
		grad[y]++;
		Graf[x].push_back(y);
	}

	for(i=0; i<n; ++i)
	{
		if(!grad[i])
		{
			grad[i] = -1;
			C.push(i);
		}
	}

	while(!C.empty())
	{
		int nod = C.front(); C.pop();
		ordonate.push_back(nod);
		for(auto v : Graf[nod])
		{
			grad[v]--;
			if(!grad[v])
			{
				grad[v] = -1;
				C.push(v);
			}
		}
	}
	for(auto j : ordonate)
		out << j << " ";

	in.close();
	out.close();

	return 0;
}