Cod sursa(job #1705894)

Utilizator roby10roby10 roby10 Data 21 mai 2016 02:00:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <cstdio>
#include <vector>

#define Nmax 50002

using namespace std;

long N,M;
long vizitat[Nmax];

vector<long> sol;

vector< vector<long> > adj_mat(Nmax, vector<long>());

void dfs(long s)
{
	if(vizitat[s]) 
		return;

	vizitat[s] = 1;

	for(long i = 0 ; i < adj_mat[s].size(); i++)
		dfs(adj_mat[s][i]);
	

	vizitat[s] = 2;

	sol.push_back(s);





}
int main()
{
	FILE *fin = fopen("sortaret.in" , "r");
	FILE *fout = fopen("sortaret.out" , "w");


	fscanf(fin, "%li %li", &N, &M);


	long a,b;

	for(long i = 0; i < M; i++)
	{
		fscanf(fin,"%li %li", &a, &b);
		adj_mat[a].push_back(b);
	}

	for(long i = 1; i <= N; i++)
		if(!vizitat[i])
			dfs(i);

	for(long i = sol.size()-1; i > -1 ; i--)
		fprintf(fout,"%li ", sol[i]);

	fprintf(fout,"\n");


	fclose(fin);
	fclose(fout);
}