Cod sursa(job #520435)

Utilizator lcodrutlucianLazar Codrut-Lucian lcodrutlucian Data 8 ianuarie 2011 16:21:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
using namespace std;

const int MAXN = 50000+1;

struct Node{
	int v;
	Node* next;

	Node(int v, Node* next):
		v(v), next(next) {
	}
};

int n,m;
Node* vec[MAXN];
Node* sol;
int visited[MAXN];

void visitDF(int v){
	visited[v]=true;
	for(Node* node = vec[v]; node; node = node->next){
		if(!visited[node->v]){
			visitDF(node->v);
		}
	}
	sol = new Node(v,sol);
}

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");

	in >> n >> m;
	int v1, v2;
	Node* node;
	for(;m>0;--m){
		in >> v1 >> v2;
		vec[v1] = new Node(v2, vec[v1]);
	}

	for(int i=1;i<=n;i++){
		if(!visited[i]){
			visitDF(i);
		}
	}

	for(node=sol; node; node = node->next){
		out << node->v << " ";
	}
	out << "\n";

	in.close();
	out.close();
	return 0;
}