Cod sursa(job #527442)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 31 ianuarie 2011 16:37:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const char iname[] = "sortaret.in";
const char oname[] = "sortaret.out";
const int  nmax    = 50024;

ifstream fin(iname);
ofstream fout(oname);

int i, j, v[nmax], incoming[nmax], n, m, x, y, viz[nmax], sol[nmax], pas, k;
vector<int> Gr[nmax];

void DF(int nod)
{	
	viz[nod] = 1;
	for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++it)
		if(viz[*it] == 0)
			DF(*it);
	sol[++pas] = nod;
	
}

int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y;
		Gr[x].push_back(y);
		incoming[y]++;
	}
	
	for(i = 1; i <= n; i ++)
		if(incoming[i] == 0)
			v[++k] = i;
		
	for(i = 1; i <= k; i ++)
			DF(v[i]);
	for(i = n; i >= 1; i --)
		fout << sol[i] << " ";
	return 0;
}