Cod sursa(job #1344760)

Utilizator paftenieAdrian Pop paftenie Data 16 februarie 2015 22:55:03
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

typedef struct node {
	int to;
	node *next;
} *pnode;

const int MAX = 50000;

int n, m;
pnode graf[MAX];
char visited[MAX];
int sol[MAX];
int count;

void add(int from, int to) {
	pnode n = new node;
	n->to = to;
	n->next = graf[from];
	graf[from] = n;
}

void push(int n) {
	sol[count] = n;
	count++;
}

void df(int current) {
	visited[current] = 1;
	
	pnode p = graf[current];
	while (p) {
		if (visited[p->to] == 0) {
			df(p->to);
		}
		p = p->next;
	}
	
	push(current);
}

void sort() {
	for (int i = 0; i < n; i++) {
		if (visited[i] == 0) {
			df(i);
		}
	}
}

int main() {
	fin >> n >> m;
	
	int from, to; 
	for (int i = 0; i < m; i++) {		
		fin >> from >> to;
		add(from, to);
	}
	
	sort();
	
	for (int i = count - 1; i > 0; i--) {
		fout << sol[i] << ' ';
	}
	
	fin.close();
	fout.close();
	return 0;
}