#include "pch.h"
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;

class graph
{
	int n;

	list<int> *adj;

	void DFSUtil(int v, bool visited[]);
	void TopologicalSortUtil(int v, bool visited[], stack<int> &stack);
public:
	graph(int nr);
	graph(const char* file);

	void addEdge(int v, int w);

	void DFS(int src);
	void TpS();
	void TpS(const char* file);
};

graph::graph(int nr)
{
	this->n = nr;
	this->adj = new list<int>[nr];
}

graph::graph(const char* file)
{
	this->n = 0;
	ifstream f(file);

	this->adj = new list<int>[100];

	while (!f.eof())
	{
		int a, b;
		f >> a >> b;
		addEdge(a, b);
		this->n++;
	}
	f.close();
}

void graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
}

void graph::DFSUtil(int v, bool visited[])
{
	visited[v] = true;
	cout << v << " ";

	list<int>::iterator it;
	for (it = adj[v].begin(); it != adj[v].end(); ++it)
		if (visited[*it] == false)
			DFSUtil(*it, visited);
}

void graph::DFS(int src)
{
	bool *visited = new bool[n];

	for (int i = 0; i < n; i++)
		visited[i] = false;

	DFSUtil(src, visited);
}

void graph::TopologicalSortUtil(int v, bool visited[], stack<int> &stack)
{
	visited[v] = true;

	list<int>::iterator it;
	for (it = adj[v].begin(); it != adj[v].end(); ++it)
		if (visited[*it] == false)
			TopologicalSortUtil(*it, visited, stack);

	stack.push(v);
}

void graph::TpS()
{
	stack<int> Stack;

	bool *visited = new bool[n];

	for (int i = 0; i < n; i++)
		visited[i] = false;

	for (int i = 0; i < n; i++)
		if (visited[i] == false)
			TopologicalSortUtil(i, visited, Stack);

	while (!Stack.empty())
	{
		cout << Stack.top() << " ";
		Stack.pop();
	}
}

void graph::TpS(const char* file)
{
	stack<int> Stack;

	bool *visited = new bool[n];

	for (int i = 1; i <= n; i++)
		visited[i] = false;

	for (int i = 1; i <= n; i++)
		if (visited[i] == false)
			TopologicalSortUtil(i, visited, Stack);

	ofstream g(file);
	while (!Stack.empty())
	{
		g << Stack.top() << " ";
		Stack.pop();
	}
	g.close();
}

int main()
{
	graph g("sortaret.in");
	g.TpS("sortaret.out");
}