Cod sursa(job #148754)

Utilizator c_sebiSebastian Crisan c_sebi Data 4 martie 2008 19:51:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

#define MAXN 50001

struct nod{
	int inf;
	nod *urm;
} *G[MAXN];

int n, m, deg[MAXN], Q[MAXN], k;

void add(int x, int y){
	nod *p = new nod;
	p->inf = y;
	p->urm = G[x];
	G[x] = p;
}


void read(){
	int x, y, i;
	FILE *f=fopen("sortaret.in", "r");
	fscanf(f, "%d %d", &n, &m);
	for(i=0; i<m; i++){
		fscanf(f, "%d %d", &x, &y);
		add(x, y);
		deg[y]++;
	}
	fclose(f);
}


void sort_top(){
	int i, pr, x;
	nod *p;
	for(i=1; i<=n; i++)
		if(!deg[i])
			Q[k++]=i;
	pr=0;
	while(pr<=k){
		x = Q[pr++];
		for(p=G[x]; p; p=p->urm){
			deg[p->inf]--;
			if(!deg[p->inf]) Q[k++]=p->inf;
		}
	}
}



int main(){
	FILE *g=fopen("sortaret.out", "w");
	read();
	sort_top();
	for(int i=0; i<k; i++)
		fprintf(g, "%d ", Q[i]);
	fclose(g);
	return 0;
}