#include <iostream>
#include <fstream>
#include <string>
#include <vector>

struct goveman{						//структура описания "чиновника" который выдает справки
	std::vector<char> canTake;		//какие справки он может выдать
	std::vector<char> needIt;		//какие справки необходимы что бы он выдал справки
	int ver;						//номер вершины, так как у нас все это представление в виде графа
};

class topological{
private:
	goveman	*inform;				//объявление массива структур
	int countofver;					//количество вершин
	bool *visited;					//массив "посещеных вершин"
	bool **graph;					//матрица смежности нашего графа
	int *result;					//оптимальный результат
	int step = 0;					//необходимая переменная для некоторых манипуляций
	std::string loadfilename;		//имя файла откуда загружать
	std::string savefilename;		//имя файла куда сохранять
public:
	topological(std::string loadfilename, std::string savefilename);		//конструктор класса
	void loadfromfile();													//функция загрузки из файла
	void parceit(char *string);												//функция разделения строки на необходимые для нас части
	void analistateit();													//анализ полученных данных в граф
	void mainalgo();														//главный алгоритм
	void savetofile();														//сохранение в файл
	void deepfind(int ver);													//поиск в глубину в графе
};

topological::topological(std::string loadfilename, std::string savefilename){
	this->loadfilename = loadfilename;		//присвоение имени
	this->savefilename = savefilename;		//присвоение имени
}

void topological::loadfromfile(){
	//открытие файла с нашим представлением чиновников
	std::ifstream fin;
	fin.open(loadfilename.c_str());
	int counter = 0;
	char buff[1024];
	//подсчет количества строк в файле - кол-во строк = кол-ву вершин
	while (!fin.eof()){
		fin.getline(buff, 1024, '\n');
		counter++;
	}
	//выделение всех необходимых мест в памяти под необходимые массивы
	inform = new goveman[counter];
	graph = new bool*[counter];
	for (int i = 0; i < counter; i++){
		graph[i] = new bool[counter];
	}
	fin.seekg(0, fin.beg);					//переходим обратно в начало файла
	for (int i = 0; i < counter; i++){
		for (int j = 0; j < counter; j++){
			graph[i][j] = 0;				//так как у нас массив с графом "пустой" - в нем нет никаких значений кроме нижней границы байта блять чтоли заполняем его нулями
		}
	}
	countofver = counter;
	result = new int[counter];
	visited = new bool[counter];
	//начинаем ебарить каждую строчку файла чтобы вынуть необходимые для нас вещи
	while (!fin.eof()){
		fin.getline(buff, 1024, '\n');
		parceit(buff);
	}
}

void topological::parceit(char *string){		//функция разделения я тебе ее рассказывал
	bool hook = false;
	for (int i = 0; i < strlen(string); i++){
		if (string[i] >= '0' && string[i] <= '9')
			inform[step].ver = string[i] - 48;
		if (string[i] == '|')
			hook = true;
		if (hook==false && (string[i] >= 'A' && string[i] <= 'Z')){
			inform[step].canTake.push_back(string[i]);
		}
		if (hook == true && (string[i] >= 'A' && string[i] <= 'Z')){
			inform[step].needIt.push_back(string[i]);
		}
	}
	step++;
}

void topological::analistateit(){		//функция построения графа тоже рассказывал
	step = 0;
	for (int i = 0; i < countofver; i++){
		for (int j = 0; j < countofver; j++){
			for (int k = 0; k < inform[i].needIt.size(); k++){
				for (int p = 0; p < inform[j].canTake.size(); p++){
					if (inform[i].needIt[k] == inform[j].canTake[p]){
						graph[j][i] = 1;
					}
				}
			}
		}
	}
}

void topological::mainalgo(){
	for (int i = 0; i < countofver; i++)
		visited[i] = false;
	for (int i = 0; i < countofver; i++){
		if (!visited[i]){
			deepfind(i);
		}
	}
	//переворачиваем массив
	for (int i = 0, j = countofver - 1; i < j; i++, j--){
		int tmp = result[i];
		result[i] = result[j];
		result[j] = tmp;
	}
	for (int i = 0; i < countofver; i++)
		std::cout << result[i] << " ";
}

void topological::deepfind(int ver){
	visited[ver] = true;
	for (int i = 0; i < countofver + 1; i++){
		if (graph[ver][i] && !visited[i]){
			deepfind(i);
		}
	}
	result[step] = ver;
	step++;
}

void topological::savetofile(){
	bool **buffer = new bool*[countofver];
	for (int i = 0; i < countofver; i++){
		buffer[i] = new bool [countofver];
	}
	for (int i = 0; i < countofver; i++){
		for (int j = 0; j < countofver; j++){
			buffer[i][j] = graph[result[i]][j];
		}
	}
	for (int i = 0; i < countofver; i++){
		for (int j = 0; j < countofver; j++){
			graph[i][j] = buffer[i][result[j]];
		}
	}
	std::ofstream file(savefilename.c_str());
	file << "digraph {\n";
	file << "rankdir=LR;" << std::endl;
	for (int i = 0; i < countofver - 1; i++){
		file << result[i]+1 << "->" << result[i + 1]+1 << ";" << std::endl;
	}
	file << "}\n";
	file.close();
}

int main(){
	topological object("time.txt", "out.txt");
	object.loadfromfile();
	object.analistateit();
	object.mainalgo();
	object.savetofile();
	return 0;
}