/**
	Топологично сортиране на DAG
		Редица, от всички върхове на DAG-а, такава че ако u е преди v в редицата, то няма ребро (v,u).

	Използва редуцирана версия на DFS() и извежда върховете в обратно сортиран, спрямо finalized[] ред.
*/

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

const int n = 9;

vector<int> graph[n] = { { 2, 3, 4, 7 }, { 3, 5 }, { 1, 8 }, { 6, 7 }, { 8 }, {}, { 4 }, { 5 }, {} };

pair<int, int> finalized[n];
bool visited[n];
int time;

void DFS_visit(int u)
{
	visited[u] = true;
	++time;

	for (int v : graph[u]) if (!visited[v]) DFS_visit(v);

	finalized[u] = pair<int, int>(u, ++time);
}

void DFS()
{
	time = 0;
	for (int i = 0; i < n; i++) visited[i] = false;
	for (int i = 0; i < n; i++) if (!visited[i]) DFS_visit(i);
}

void DAG_Toposort()
{
	DFS();

	sort(finalized, finalized + n, [](pair<int, int> p1, pair<int, int> p2){return p1.second > p2.second; });

	for (int i = 0; i < n; i++) cout << finalized[i].first << " ";
}

int main()
{
	DAG_Toposort();

	cout << endl;

	return 0;
}