Cod sursa(job #1816912)

Utilizator adu18sptAndrei Mircea adu18spt Data 27 noiembrie 2016 08:50:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <vector>

using namespace std;

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


vector<int> v[50010];
int grad[50010],q[50010];

int main()
{
	int n,m,x,y,nr=0;
	
	
	fin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		fin>>x>>y;
		
		v[x].push_back(y);
		grad[y]++;
		
	}
	
	for(int i=1;i<=n;i++)
	{
		if(grad[i]==0){
			q[++nr]=i;
		}
	}
	
	for(int i=1;i<=nr;i++)
	{
		for(vector<int>::iterator it=v[q[i]].begin();it!=v[q[i]].end();it++)
			if(--grad[*it]==0)
				q[++nr]=*it;
	}
	
	for(int i=1;i<=nr;i++)
		fout<<q[i]<<" ";
	
	return 0;
}