Cod sursa(job #322649)

Utilizator GulyanAlexandru Gulyan Data 9 iunie 2009 15:46:03
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct{
	int cul;
	int *vec;
	int m;
}Nod;

typedef struct{
	int s, d;
}Arc;

#define ALB 0
#define GRI 1
#define NEGRU 2

int main(int argc, char *argv[])
{
	//deschidere fisiere
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	//declarare date, initializare, citire si alocare de memorie
	Nod *v;
	Arc *a;
	int n, m, i, j, k, l, vf, vf1;
	scanf("%d%d", &n, &m);
	n++;
	v = (Nod*)malloc( sizeof(*v) * n );
	a = (Arc*)malloc( sizeof(*a) * m );
	int *laf, *la;
	laf = la = (int*)malloc( sizeof(int) * m );
	int *S = (int*)malloc( sizeof(int) * n );
	int *S1 = (int*)malloc( sizeof(int) * n );
	for( i = 0; i < n; i++){
		v[i].cul = ALB;
		v[i].m = 0;
	}
	for( i = 0; i < m; i++){
		scanf("%d%d", &a[i].s, &a[i].d);
		v[a[i].s].m++;
	}

	//crearea listelor de adiacenta
	for( i = 0; i < n; i++){
		v[i].vec = la;
		la += v[i].m;
		v[i].m = 0;
	}
	for( i = 0; i < m; i++){
		for( j = 0; j < v[a[i].s].m; j++)
			if(v[a[i].s].vec[j] == a[i].d)
				continue;
		v[a[i].s].vec[v[a[i].s].m++] = a[i].d;
	}

	vf = 0;
	for( l = 1; l < n; l++){
		if(v[l].cul == ALB){
			//Parcurgere DFS
			S1[vf1 = 0] = l;
			while(vf1 >= 0){
				i = S1[vf1--];
				v[i].cul = GRI;
				for( j = v[i].m ; j--; ){
					k = v[i].vec[j];
					if(v[k].cul == ALB)
						S1[++vf1] = k;
				}
				v[i].cul = NEGRU;
				S[vf++] = i;
			}
		}
	}

	for( i = 0; i < vf; i++)
		printf("%d ", S[i]);

	//eliberare memorie
	free( a );
	free( v );
	free( S );
	free( S1 );
	free( laf );
	return 0;
}