fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class Graph {
  7.     int V; // Number of vertices
  8.     vector<vector<int>> adjList; // Adjacency list
  9.  
  10.     // Helper function for DFS to detect cycles
  11.     bool dfs(int node, vector<bool>& visited, vector<bool>& recStack) {
  12.         // Mark the current node as visited and add it to the recursion stack
  13.         visited[node] = true;
  14.         recStack[node] = true;
  15.  
  16.         // Iterate over all the neighbors of the current node
  17.         for (int neighbor : adjList[node]) {
  18.             // If the neighbor is not visited, recurse
  19.             if (!visited[neighbor]) {
  20.                 if (dfs(neighbor, visited, recStack)) {
  21.                     return true;
  22.                 }
  23.             }
  24.             // If the neighbor is already in the recursion stack, a cycle is detected
  25.             else if (recStack[neighbor]) {
  26.                 return true;
  27.             }
  28.         }
  29.  
  30.         // Remove the current node from the recursion stack
  31.         recStack[node] = false;
  32.         return false;
  33.     }
  34.  
  35. public:
  36.     // Constructor
  37.     Graph(int V) {
  38.         this->V = V;
  39.         adjList.resize(V);
  40.     }
  41.  
  42.     // Function to add an edge to the graph
  43.     void addEdge(int u, int v) {
  44.         adjList[u].push_back(v);
  45.     }
  46.  
  47.     // Function to check if the graph contains a cycle
  48.     bool hasCycle() {
  49.         vector<bool> visited(V, false);  // To keep track of visited nodes
  50.         vector<bool> recStack(V, false); // To keep track of nodes in the recursion stack
  51.  
  52.         // Perform DFS for each node to detect cycles
  53.         for (int i = 0; i < V; i++) {
  54.             if (!visited[i]) {
  55.                 if (dfs(i, visited, recStack)) {
  56.                     return true;
  57.                 }
  58.             }
  59.         }
  60.         return false;
  61.     }
  62. };
  63.  
  64. int main() {
  65.     Graph g(4);
  66.     g.addEdge(0, 1);
  67.     g.addEdge(1, 2);
  68.     g.addEdge(2, 0); // This creates a cycle
  69.     g.addEdge(2, 3);
  70.  
  71.     if (g.hasCycle()) {
  72.         cout << "Graph contains a cycle" << endl;
  73.     } else {
  74.         cout << "Graph does not contain a cycle" << endl;
  75.     }
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Graph contains a cycle
https://ideone.com/6SvxAB
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!