Cod sursa(job #830654)

Utilizator bulbulicaAlexandrescu Cristian bulbulica Data 7 decembrie 2012 12:21:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <vector>
#include <fstream>
#define NMAX 50001
using namespace std;
vector <int> v[NMAX];
int n,m,S;
int solutie[NMAX],t[NMAX];

ifstream f("sortaret.in");
ofstream g("sortaret.out");

void citire()
{
	int i,x,y;
	f>>n>>m;
	for (i=1;i<=m;++i)
	{
		f>>x>>y;
		v[x].push_back(y);
	}
}
void dfs(int k)
{
	t[k]=1;
	for (unsigned int i=0;i<v[k].size();++i)
		if (t[v[k][i]]==0)
			dfs(v[k][i]);
	solutie[++S]=k;
}
void sortare_top()
{
	for (int i=1;i<=n;++i)
		if (t[i]==0)
			dfs(i);
}
int main()
{
	citire();
	sortare_top();
	for (int i=S;i>=1;i--)
		g<<solutie[i];
	return 0;
}