Cod sursa(job #265137)

Utilizator c_sebiSebastian Crisan c_sebi Data 23 februarie 2009 13:59:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#define NMAX 50001

int n, m;
int viz[NMAX];

struct nod{
	int val;
	nod *urm;
} *G[NMAX+1];

void add(int unde, int peCine){
	nod *p = new nod;
	p->val = peCine;
	p->urm = G[unde];
	G[unde] = p;
}

void df(int k){
	nod *q;
	viz[k] = 1;
	for(q = G[k]; q; q=q->urm)
		if(!viz[q->val])
			df(q->val);
	add(n+1, k);
}

int main(){
	int x, y, i;
	FILE *f = fopen("sortaret.in", "r");
	FILE *g = fopen("sortaret.out", "w");
	fscanf(f, "%d %d", &n, &m);
	for(i = 0; i < m; i++){
		fscanf(f, "%d %d", &x, &y);
		add(x, y);
	}
	for(i = 1; i <= n; i++)
		if(!viz[i])
			df(i);
	nod *q;
	for(q = G[n+1]; q; q = q->urm)
		fprintf(g, "%d ", q->val);
	fclose(f);
	fclose(g);
	return 0;
}