Cod sursa(job #1894002)

Utilizator rosuflaRosu Flaviu rosufla Data 26 februarie 2017 12:57:33
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
// Topological sort.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
stack<int> date;

void DFS(list<int> *adj, bool visited[], int i) {
	visited[i] = true;
	list<int>::iterator it;
	for (it = adj[i].begin(); it != adj[i].end(); it++) {
		if (visited[*it] == false)
			DFS(adj, visited, *it);
	}
	if (i != 0)
		date.push(i);
}

void DFS_until(list<int> *adj, bool visited[], int v) {
	for (int i = 0; i < v; ++i)
		if (visited[i] == false) 
			DFS(adj, visited, i);

	while (!date.empty()) {
		g << date.top() << " ";
		date.pop();
	}
	g << "\n";
}

int main(){
	int v,edges,a,b;
	f >> v >> edges;
	list<int> *adj = new list<int>[v];
	for (int i = 0; i < edges; ++i) {
		f >> a >> b;
		adj[a].push_back(b);
	}
	bool *visited = new bool[v];
	for (int i = 0; i < v; ++i)
		visited[i] = false;
	DFS_until(adj, visited, v);
    return 0;
}