Cod sursa(job #651321)

Utilizator vladbaesuVlad Baesu vladbaesu Data 20 decembrie 2011 08:12:54
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<stdlib.h>
#define NRNOD 100000

typedef struct Nod
{	
	int info; 
	struct Nod *next;

} Nod;
Nod *G[NRNOD];
int vizitat[NRNOD],n,m,k,srt[NRNOD];

void dfs(int x)
{
	Nod *p;
	vizitat[x]=1;
	for(p=G[x];p;p=p->next)
	if(!vizitat[p->info]) dfs(p->info);
	
	srt[++k]=x;
}

int main()
{
	FILE *intrare,*iesire;
	int i,x,y;
	intrare=fopen("srtaret.in","r");
	iesire=fopen("srtaret.out","w");
	fscanf(intrare,"%d %d",&n,&m);

	for(i=1;i<=m;i++)
	{
		fscanf(intrare,"%d %d",&x,&y);
		Nod *p;
		if(!(p=(Nod*)malloc(sizeof(Nod)))) return 1;
		p->info=y;
		p->next=G[x];
		G[x]=p;
	}

	for(i=1;i<=n;i++) if(vizitat[i]==0) dfs(i); 
	for(i=n;i>=1;i--) fprintf(iesire,"%d ",srt[i]);
	fclose(intrare);fclose(iesire);
	return 0;   
}