Cod sursa(job #709996)

Utilizator fhandreiAndrei Hareza fhandrei Data 8 martie 2012 19:18:35
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
//Include
#include <stdio.h>
#include <vector>
using namespace std;

//Constante
const int MAX_SIZE = 50000;

//Functii
void dfs(int start);

//Variabile
FILE *in, *out;

int nrNoduri, nrMuchii;

vector<bool> vizitat;
vector<int> precedenti[MAX_SIZE], urmatori[MAX_SIZE];

//Main
int main()
{
	in = fopen("sortaret.in","rt");
	out = fopen("sortaret.out","wt");
	fscanf(in, "%d%d", &nrNoduri, &nrMuchii);
	
	vizitat.resize(nrNoduri+1);
	int cFrom, cTo;
	for(int i=1 ; i<=nrMuchii ; ++i)
	{
		fscanf(in, "%d%d", &cFrom, &cTo);
		urmatori[cFrom].push_back(cTo);
		precedenti[cTo].push_back(cFrom);
	}
	
	for(int i=1 ; i<=nrNoduri ; ++i)
		dfs(i);
	
	
	fclose(in);
	fclose(out);
	return 0;
}

void dfs(int start)
{
	if(vizitat[start])
		return ;
	
	vector<int>::iterator it, end;
	
	end=precedenti[start].end();
	for(it=precedenti[start].begin() ; it!=end ; ++it)
		if(!vizitat[*it])
			return ;
	
	vizitat[start] = true;
	fprintf(out, "%d ", start);
	
	end=urmatori[start].end();
	for(it=urmatori[start].begin() ; it!=end ; ++it)
		dfs(*it);
	
}