Cod sursa(job #2423193)

Utilizator toni123Mititelu George-Antonio toni123 Data 20 mai 2019 21:42:53
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#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, 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] == 0)
		{
			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] == 0)
			{
				grad[v] = -1;
				C.push(v);
			}
		}
	}
	for(i=0 ; i<ordonate.size(); i++)
        out << ordonate[i]+1 << " ";

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

	return 0;
}