Cod sursa(job #1127827)

Utilizator bogdanrusRus Bogdan bogdanrus Data 27 februarie 2014 13:59:48
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>

#define NMax 50000

int M, N, A[NMax][NMax], R[NMax], Viz[NMax];

void sortare () {	
	int i, j, index, root;
	
	index=0;

	for (i=1; i<=N; ++i) {
		root=1;
		for (j=1; j<=N; ++j) {
			if (A[j][i] == 1) {
				root=0;
				break;
			}
		}
		if (root==1) {
			index++;
			R[index] = i;
			Viz[i]=1;
			printf("root = %d index = %d \n",i, index);
		}
	}
	
	for (j=1; j<=index; ++j) {
		for (i=1; i<=N; ++i) {
			if ((A[R[j]][i] == 1)&&(Viz[i]==0)) {
				index++;
				R[index] = i;
				Viz[i] = 1;
			}
		}
	}
	
	for(i=1; i<=N; ++i) {
		printf("%d ",R[i]);
	}

}


int main (void) {
	
	int i,j,p,q;
		
	freopen("sortare.in","r",stdin);
	freopen("sortare.out","w",stdout);
	
	scanf("%d %d", &N, &M); 
	
	for (p = 1; p<=N; ++p) {
		Viz[p]=0;
		R[p]=0;
		for (q = 1; p<=N; ++p)
			A[p][q] = 0;
	}
	
	for (p = 1; p<=M; ++p) {
		scanf("%d %d",&i, &j);
		A[i][j] = 1;
	}
		
	sortare();

return 0;
}