Cod sursa(job #552308)

Utilizator sebii_cSebastian Claici sebii_c Data 12 martie 2011 08:03:39
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <stdlib.h>
#define NMax 50000

int M, N, len;
int *A[50000], result[50000], viz[50000];

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

void DFS(int x)
{
	int i;
	viz[x] = 1;
	for (i=1; i<=A[x][0]; ++i)
		if (!viz[A[x][i]])
			DFS(A[x][i]);
	result[++len] = x;
}

int main()
{
	int i;
	FILE *fout = fopen("sortaret.out", "w");
	Citire();
	for (i=1; i<=N; ++i)
		if (!viz[i])
			DFS(i);
	for (i=len; i>0; --i)
		fprintf(fout, "%d ", result[i]);
	return 0;
}