Cod sursa(job #651015)

Utilizator FIIAndCocRotAndrei Alexandra FIIAndCocRot Data 19 decembrie 2011 16:37:20
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<stdlib.h>

#define MAX 100003

FILE *f, *g;

int N, M, viz[MAX], index, sorttop[MAX], index1;


typedef struct Node 
{	int info; 
	struct Node *next;
} Node;
Node *a[MAX];

void file_open ()
{	f=fopen("sorttop.in", "r");
	g=fopen("sorttop.out", "w");
}


void file_close ()
{	fclose (f);
	fclose(g);
}

int add (int n1, int n2)
{	Node *ptr;
	if(!(ptr=(Node*)malloc(sizeof(Node))))
		return 0;
	ptr->info=n2;
	ptr->next=a[n1];
	a[n1]=ptr;
	return 1;
}

void read_node ()
{ 	int n1, n2;
	for(index=0; index<M; index++)
	{fscanf(f,"%d%d", &n1, &n2);
	 if(!(add(n1,n2)))
		{printf("eroare");
		 return ;
		}
	}
}

void write ()
{	for (index=1;index<=N;index++)
		fprintf(g, "%d " , sorttop[index]);
}


void DFS(int S)
{	Node *p;
	viz[S]=1;
   	for(p=a[S]; p!=NULL; p=p->next)
     		if(viz[p->info]==0)
		     DFS(p->info);
	index1--;
	sorttop[index1]=S;
			
}	



int main ()
{	file_open();
	fscanf(f,"%d %d", & N, &M);
	read_node();
	index1=N+1;
	for(index=1;index<=N;index++)
	if(viz[index]==0)
		DFS(index);
	write();
	file_close();
	return 0;
}