Cod sursa(job #526912)

Utilizator Gaby_mMititelu Gabriel Gaby_m Data 29 ianuarie 2011 19:35:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<cstdio>

using namespace std;

struct list {
	int neigh;
	list *next;
};

list *listad[50001];
int N, M;
bool viz[50001];
list *rez;

void readData() {
	
	scanf("%d %d", &N, &M);
	int x, y;
	for (int i = 0; i < M; i++) {
		scanf("%d %d ", &x, &y);

		list *aux = new list;
		aux->neigh = y;
		aux->next = listad[x];
		listad[x] = aux;		
	}
}


void dfs(int source){
	viz[source] = 1;
	list *aux = listad[source];
	while (aux) {
		if (!viz[aux->neigh]) {			
			dfs(aux->neigh);
		}
		aux = aux->next;
	}

	aux = new list;
	aux->neigh = source;
	aux->next = rez;
	rez = aux;
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	readData();
	rez = NULL;

	for (int i = 1; i <= N; i++) {
		if (!viz[i]) dfs(i);
	}

	while (rez) {
		printf("%d ", rez->neigh);
		rez = rez->next;
	}

	printf("\n");


	return 0;
}