Cod sursa(job #477924)

Utilizator azotlichidAdrian Vladu azotlichid Data 16 august 2010 17:31:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
using namespace std;

#define NMAX 50005

vector<int> adj[NMAX];
list<int> r;
int N, M;
int u[NMAX];

void dfs(int v) {
	u[v] = 1;
	for (vector<int> :: iterator it = adj[v].begin(); it != adj[v].end(); it++)
		if (!u[*it])
			dfs(*it);
	r.push_front(v);
}

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	scanf("%d %d", &N, &M);
	int i, j;
	for (int k = 0; k < M; k++) {
		scanf("%d %d", &i, &j);
		adj[i].push_back(j);
	}
	memset(u, 0, sizeof(u));
	for (int i = 1; i <= N; i++)
		if (!u[i])
			dfs(i);
	for (list<int> :: iterator it = r.begin(); it != r.end(); it++)
		printf("%d ", *it);
	printf("\n");
	return 0;
}