Cod sursa(job #2429984)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 12 iunie 2019 10:02:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int nmax = 50005;
vector<int>muchii_in[nmax];
vector<int>muchii_out[nmax];
queue<int>q;
stack<int>rasp;
int grad[nmax];

int main()
{
	ifstream cin("sortaret.in");
	ofstream cout("sortaret.out");
	int a, b, n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b;
		muchii_in[b].push_back(a);
		muchii_out[a].push_back(b);
		grad[a]++;
	}
	for (int i = 1; i <= n; i++)
		if (grad[i] == 0)
		{
			q.push(i);
			rasp.push(i);
		}
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < muchii_in[x].size(); i++)
		{
			int tata = muchii_in[x][i];
			grad[tata]--;
			if(grad[tata]==0)
			{
				q.push(tata);
				rasp.push(tata);
			}
		}
	}
	while (!rasp.empty())
	{
		cout << rasp.top() << " ";
		rasp.pop();
	}
	return 0;
}