Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement