Cod sursa(job #156556)

Utilizator zobicaMarin Marin zobica Data 12 martie 2008 17:02:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

int n, m;
struct nod {
	int x;
	nod *urm;	
}; 
nod *p[50001], *S;
int viz[50001];

void adaug(nod *&p, int y){
	nod *q = new nod;
	q -> x = y;
	q -> urm = p;
	p = q;
}

void citire(){
	freopen("sortaret.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adaug(p[x],y);
	}
	fclose(stdin);
}

void df(int x) {
	viz[x] = 1; 
	for (nod *q = p[x]; q; q = q -> urm) 
		if (!viz[q -> x])	{
			df(q -> x);
			adaug(S, q -> x);		
		}
}

void top() {
	freopen("sortaret.out", "w", stdout);	
	for (nod *q = S; q; q = q -> urm) 
		printf("%d ", q -> x);	
	fclose(stdout);
}

int main() {
	citire();
	for (int i = 1; i <= n ; i ++) 
		if (!viz[i]) {
			adaug(S, i);		
			df(1);
		}
		top();
		return 0;
}