Cod sursa(job #404934)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 26 februarie 2010 23:03:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <vector>
#define NMAX 50010
using namespace std;

vector<int> G[NMAX];
int viz[NMAX];
vector<int> A;
int N,M;

void citire()
{
	FILE *fin=fopen("sortaret.in","r");
	
	int i,x,y;
	
	fscanf(fin,"%d %d",&N,&M);
	
	for(i=1;i<=M;i++)
	{
		fscanf(fin,"%d %d",&x,&y);
		G[x].push_back(y);
	}
	
	fclose(fin);
}

void tsort(int x)
{
	unsigned int i;
	if(!viz[x])
	{
		viz[x]++;
		for(i=0;i<G[x].size();i++)
			tsort(G[x][i]);
		A.push_back(x);
	}
}


void afisare()
{
	int i;
	FILE *fout=fopen("sortaret.out","w");
	
	for (i=A.size()-1;i>=0;i--)
		fprintf(fout,"%d ",A[i]);
	
	fclose(fout);
	
}


int main()
{
	citire();
	
	int i;
	
	for(i=1;i<=N;i++)
		tsort(i);
	
	afisare();
	
}