Cycle Detection

#include<iostream>
#include<vector>
#include<list>
#include <queue>
// INPUTS:
//    7
//    8
//
//    0 1 1
//    1 1 2
//    0 1 2
//    1 1 3
//    2 1 4
//    3 1 4
//    4 1 5
//    5 1 6


//Cycle Detection Input
//	  7
//	  8
//
//	  0 1 1
//	  1 1 2
//	  2 1 0
//	  1 1 3
//	  2 1 4
//	  3 1 4
//	  4 1 5
//	  5 1 6



struct Vertex
{
	int weight;
	int vertex_number;

	Vertex(int weight, int vertex_number)
	{
		this->weight = weight;
		this->vertex_number = vertex_number;
	}
};


//undirected weight graph
std::vector<std::list<Vertex>> graph;

//TODO make bfs and dfs

bool connection_exists(int from, int to)
{
	for (auto element : graph[from])
	{
		if (element.vertex_number == to)
		{
			return true;
		}
	}

	return false;
}

void add_connection(int from, int weight, int to)
{
	if (!connection_exists(from, to))
	{
		graph[from].push_back({ weight, to });
		//graph[to].push_back({ weight, from });
	}
}

void print_graph()
{
	for (int i = 0; i < graph.size(); i++)
	{
		std::cout << "Vertex " << i << ": ";

		for (auto element : graph[i])
		{
			std::cout << element.vertex_number << "->" << element.weight << " ";
		}

		std::cout << std::endl;
	}
}


std::vector<bool> visited;

void bfs(int from)
{
	std::queue<int> next_to_process;
	next_to_process.push(from);

	while (!next_to_process.empty())
	{
		int next_index = next_to_process.front();
		next_to_process.pop();
		visited[next_index] = true;

		std::cout << next_index << " ";

		for (auto neighbor : graph[next_index])
		{
			if (!visited[neighbor.vertex_number])
			{
				visited[neighbor.vertex_number] = true;
				next_to_process.push(neighbor.vertex_number);
			}
		}
	}

	std::cout << std::endl;
}


std::vector<bool> visited_dfs;

void dfs(int from)
{
	std::cout << from << " ";
	visited_dfs[from] = true;

	for (auto neighbor : graph[from])
	{
		if (!visited_dfs[neighbor.vertex_number])
		{
			visited_dfs[neighbor.vertex_number] = true;
			dfs(neighbor.vertex_number);
		}
	}
}

std::vector<bool> visited_topo;
std::list<int>  ordered_nodes;

//DFS na svi nodes
void _recursive_topological(int from)
{
	visited_topo[from] = true;

	//go through neighbors
	for (auto element : graph[from])
	{
		if (!visited_topo[element.vertex_number])
		{
			visited_topo[element.vertex_number] = true;
			_recursive_topological(element.vertex_number);
		}
	}


	ordered_nodes.push_back(from);


}

void topological_sort()
{
	for (int i = 0; i < graph.size(); i++)
	{
		if (!visited_topo[i])
			_recursive_topological(i);
	}

	ordered_nodes.reverse();

	for (auto element : ordered_nodes)
	{
		std::cout << element << " ";
	}

	std::cout << std::endl;

}

std::vector<char> detected_nodes;
void _detect_cycle(int from,bool& has_cycle)
{
	detected_nodes[from] = 'o';

	if (has_cycle)
		return;

	for(auto element : graph[from])
	{
		if(detected_nodes[element.vertex_number] == 'u')
		{
			_detect_cycle(element.vertex_number,has_cycle);
		}
		else if(detected_nodes[element.vertex_number] =='o')
		{
			has_cycle = true;
			return;
		}
	}

	detected_nodes[from] = 'c';
}

void cycle_detection()
{
	bool has_cycle = false;

	for(int i=0;i<graph.size();i++)
	{
		if(detected_nodes[i] == 'u')
		{
			_detect_cycle(i,has_cycle);
		}
	}

	if(has_cycle)
	{
		std::cout << "Cycle detected " << std::endl;
	}
	else
	{
		std::cout<<"No cycle detected "<<std::endl;
	}
}


int main()
{
	int nodes, edges;
	std::cin >> nodes >> edges;

	graph.resize(nodes);
	visited_dfs.resize(nodes, false);
	visited.resize(nodes, false);
	visited_topo.resize(nodes, false);
	detected_nodes.resize(nodes, 'u');
	for (int i = 0; i < edges; i++)
	{
		int from, weight, to;
		std::cin >> from >> weight >> to;
		add_connection(from, weight, to);
	}


	//print_graph();

	//dfs(6);
	std::cout << std::endl;

	//bfs(6);


	//topological_sort();

	cycle_detection();

	return 0;
}