SHARE
TWEET

Cycle Detection

arsovski Jan 21st, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<list>
  4. #include <queue>
  5. // INPUTS:
  6. //    7
  7. //    8
  8. //    
  9. //    0 1 1
  10. //    1 1 2
  11. //    0 1 2
  12. //    1 1 3
  13. //    2 1 4
  14. //    3 1 4
  15. //    4 1 5
  16. //    5 1 6
  17.  
  18.  
  19. //Cycle Detection Input
  20. //    7
  21. //    8
  22. //   
  23. //    0 1 1
  24. //    1 1 2
  25. //    2 1 0
  26. //    1 1 3
  27. //    2 1 4
  28. //    3 1 4
  29. //    4 1 5
  30. //    5 1 6
  31.  
  32.  
  33.  
  34. struct Vertex
  35. {
  36.     int weight;
  37.     int vertex_number;
  38.  
  39.     Vertex(int weight, int vertex_number)
  40.     {
  41.         this->weight = weight;
  42.         this->vertex_number = vertex_number;
  43.     }
  44. };
  45.  
  46.  
  47. //undirected weight graph
  48. std::vector<std::list<Vertex>> graph;
  49.  
  50. //TODO make bfs and dfs
  51.  
  52. bool connection_exists(int from, int to)
  53. {
  54.     for (auto element : graph[from])
  55.     {
  56.         if (element.vertex_number == to)
  57.         {
  58.             return true;
  59.         }
  60.     }
  61.  
  62.     return false;
  63. }
  64.  
  65. void add_connection(int from, int weight, int to)
  66. {
  67.     if (!connection_exists(from, to))
  68.     {
  69.         graph[from].push_back({ weight, to });
  70.         //graph[to].push_back({ weight, from });
  71.     }
  72. }
  73.  
  74. void print_graph()
  75. {
  76.     for (int i = 0; i < graph.size(); i++)
  77.     {
  78.         std::cout << "Vertex " << i << ": ";
  79.  
  80.         for (auto element : graph[i])
  81.         {
  82.             std::cout << element.vertex_number << "->" << element.weight << " ";
  83.         }
  84.  
  85.         std::cout << std::endl;
  86.     }
  87. }
  88.  
  89.  
  90. std::vector<bool> visited;
  91.  
  92. void bfs(int from)
  93. {
  94.     std::queue<int> next_to_process;
  95.     next_to_process.push(from);
  96.  
  97.     while (!next_to_process.empty())
  98.     {
  99.         int next_index = next_to_process.front();
  100.         next_to_process.pop();
  101.         visited[next_index] = true;
  102.  
  103.         std::cout << next_index << " ";
  104.  
  105.         for (auto neighbor : graph[next_index])
  106.         {
  107.             if (!visited[neighbor.vertex_number])
  108.             {
  109.                 visited[neighbor.vertex_number] = true;
  110.                 next_to_process.push(neighbor.vertex_number);
  111.             }
  112.         }
  113.     }
  114.  
  115.     std::cout << std::endl;
  116. }
  117.  
  118.  
  119. std::vector<bool> visited_dfs;
  120.  
  121. void dfs(int from)
  122. {
  123.     std::cout << from << " ";
  124.     visited_dfs[from] = true;
  125.  
  126.     for (auto neighbor : graph[from])
  127.     {
  128.         if (!visited_dfs[neighbor.vertex_number])
  129.         {
  130.             visited_dfs[neighbor.vertex_number] = true;
  131.             dfs(neighbor.vertex_number);
  132.         }
  133.     }
  134. }
  135.  
  136. std::vector<bool> visited_topo;
  137. std::list<int>  ordered_nodes;
  138.  
  139. //DFS na svi nodes
  140. void _recursive_topological(int from)
  141. {
  142.     visited_topo[from] = true;
  143.  
  144.     //go through neighbors
  145.     for (auto element : graph[from])
  146.     {
  147.         if (!visited_topo[element.vertex_number])
  148.         {
  149.             visited_topo[element.vertex_number] = true;
  150.             _recursive_topological(element.vertex_number);
  151.         }
  152.     }
  153.  
  154.  
  155.     ordered_nodes.push_back(from);
  156.  
  157.  
  158. }
  159.  
  160. void topological_sort()
  161. {
  162.     for (int i = 0; i < graph.size(); i++)
  163.     {
  164.         if (!visited_topo[i])
  165.             _recursive_topological(i);
  166.     }
  167.  
  168.     ordered_nodes.reverse();
  169.  
  170.     for (auto element : ordered_nodes)
  171.     {
  172.         std::cout << element << " ";
  173.     }
  174.  
  175.     std::cout << std::endl;
  176.  
  177. }
  178.  
  179. std::vector<char> detected_nodes;
  180. void _detect_cycle(int from,bool& has_cycle)
  181. {
  182.     detected_nodes[from] = 'o';
  183.  
  184.     if (has_cycle)
  185.         return;
  186.  
  187.     for(auto element : graph[from])
  188.     {
  189.         if(detected_nodes[element.vertex_number] == 'u')
  190.         {
  191.             _detect_cycle(element.vertex_number,has_cycle);
  192.         }
  193.         else if(detected_nodes[element.vertex_number] =='o')
  194.         {
  195.             has_cycle = true;
  196.             return;
  197.         }
  198.     }
  199.  
  200.     detected_nodes[from] = 'c';
  201. }
  202.  
  203. void cycle_detection()
  204. {
  205.     bool has_cycle = false;
  206.  
  207.     for(int i=0;i<graph.size();i++)
  208.     {
  209.         if(detected_nodes[i] == 'u')
  210.         {
  211.             _detect_cycle(i,has_cycle);
  212.         }
  213.     }
  214.  
  215.     if(has_cycle)
  216.     {
  217.         std::cout << "Cycle detected " << std::endl;
  218.     }
  219.     else
  220.     {
  221.         std::cout<<"No cycle detected "<<std::endl;
  222.     }
  223. }
  224.  
  225.  
  226. int main()
  227. {
  228.     int nodes, edges;
  229.     std::cin >> nodes >> edges;
  230.  
  231.     graph.resize(nodes);
  232.     visited_dfs.resize(nodes, false);
  233.     visited.resize(nodes, false);
  234.     visited_topo.resize(nodes, false);
  235.     detected_nodes.resize(nodes, 'u');
  236.     for (int i = 0; i < edges; i++)
  237.     {
  238.         int from, weight, to;
  239.         std::cin >> from >> weight >> to;
  240.         add_connection(from, weight, to);
  241.     }
  242.  
  243.  
  244.     //print_graph();
  245.  
  246.     //dfs(6);
  247.     std::cout << std::endl;
  248.  
  249.     //bfs(6);
  250.  
  251.  
  252.     //topological_sort();
  253.  
  254.     cycle_detection();
  255.  
  256.     return 0;
  257. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top