Cod sursa(job #2553796)

Utilizator Daniel237Jugariu Daniel Daniel237 Data 22 februarie 2020 11:55:46
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m,gi[50002],sol[50002],k;
vector <int> vec[50002];
queue <int> lista;
int main()
{
	f>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		f>>x>>y;
		gi[y]++;
		vec[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		if(!gi[i])
		{
			lista.push(i);
			gi[i]--;
		}
	while(lista.size())
	{
		int nc=lista.front();
		sol[++k]=nc;
		gi[nc]--;
		lista.pop();
		for(int i=0;i<vec[nc].size();i++)
		{
			gi[vec[nc][i]]--;
			if(gi[vec[nc][i]]==0)
				lista.push(vec[nc][i]);
		}
	}
	for(int i=1;i<=n;i++)
		g<<sol[i]<<' ';
	return 0;
}