#include "graph.h"

using namespace std;

void read_input(const char* file_name, Graph* G){
	std::ifstream file_stream(file_name);
	file_stream >> G->N >> G->M;
	G->init_costs(INF);
	int i, aux1, aux2, cost;
	for(i = 0; i < G->N; i++) {
		Vertex new_node;
		new_node.p = -1;
		new_node.colour = 'w';
		new_node.content = i;
		new_node.dist = INF;
		G->nodes.push_back(new_node);
		G->degrees[i] = 0;
		std::list<int> l;
		G->adjacency_list.push_back(l);
	}
	while(file_stream >> aux1 >> aux2){
		G->adjacency_list[aux1 - 1].push_back(aux2 - 1);
		G->degrees[aux2 - 1]++;
		// G->edges.insert(make_pair(make_pair(aux1, aux2), cost));		
	}
	file_stream.close();
}

/* Kahn algorithm */
vector<int> topsort(Graph *G){
// void topsort(Graph *G){
	int node, i;
	vector<int> L, S;
	for(i = 0; i < G->N; i++){
		if(G->degrees[i] == 0)
			S.push_back(i);
	}
	while(!S.empty()){
		node = S.back();
		S.pop_back();
		std::list<int>::iterator it;
		for(it = G->adjacency_list[node].begin(); it != G->adjacency_list[node].end(); it++){
			G->degrees[*it]--;
			if(G->degrees[*it] == 0) S.push_back(*it);
		}
		G->adjacency_list[node].clear();
		L.push_back(node);
	}
	for(i = 0; i < G->N; i++){
		if(G->adjacency_list[i].size() != 0){
			cout << "Cicles found" << endl;
			break;
		}
	}
	return L;
}

void display(vector<int> v){
	ofstream out("sortaret.out");
	vector<int>::iterator it;
	for(it = v.begin(); it != v.end(); it++){
		// cout << *it << " ";
		out << *it + 1 << " ";
	}
	// cout << endl;
	out.close();
}

int main(){
	Graph G;
	read_input("sortaret.in", &G);
	// G.display_structure();
	vector<int> sorted = topsort(&G);
	display(sorted);
	// G.bfs_list(0);
	// G.dfs_list();

	// cout<<endl<<endl;
	return 0;
}