fork download
copy 
  1. // A C++ program to check if there is a cycle in 
  2. // directed graph using BFS.
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // Class to represent a graph
  7. class Graph {
  8.     int V; // No. of vertices'
  9.  
  10.     // Pointer to an array containing adjacency list
  11.     list<int>* adj;
  12.  
  13. public:
  14.     Graph(int V); // Constructor
  15.  
  16.     // function to add an edge to graph
  17.     void addEdge(int u, int v);
  18.  
  19.     // Returns true if there is a cycle in the graph
  20.     // else false.
  21.     bool isCycle();
  22. };
  23.  
  24. Graph::Graph(int V)
  25. {
  26.     this->V = V;
  27.     adj = new list<int>[V];
  28. }
  29.  
  30. void Graph::addEdge(int u, int v)
  31. {
  32.     adj[u].push_back(v);
  33. }
  34.  
  35. // This function returns true if there is a cycle
  36. // in directed graph, else returns false.
  37. bool Graph::isCycle()
  38. {
  39.     // Create a vector to store indegrees of all
  40.     // vertices. Initialize all indegrees as 0.
  41.     vector<int> in_degree(V, 0);
  42.  
  43.     // Traverse adjacency lists to fill indegrees of
  44.     // vertices. This step takes O(V+E) time
  45.     for (int u = 0; u < V; u++) {
  46.         for (auto v : adj[u])
  47.             in_degree[v]++;
  48.     }
  49.  
  50.     // Create an queue and enqueue all vertices with
  51.     // indegree 0
  52.     queue<int> q;
  53.     for (int i = 0; i < V; i++)
  54.         if (in_degree[i] == 0)
  55.             q.push(i);
  56.  
  57.     // Initialize count of visited vertices
  58.     // 1 For src Node 
  59.     int cnt = 1;
  60.  
  61.     // Create a vector to store result (A topological
  62.     // ordering of the vertices)
  63.     vector<int> top_order;
  64.  
  65.     // One by one dequeue vertices from queue and enqueue
  66.     // adjacents if indegree of adjacent becomes 0
  67.     while (!q.empty()) {
  68.  
  69.         // Extract front of queue (or perform dequeue)
  70.         // and add it to topological order
  71.         int u = q.front();
  72.         q.pop();
  73.         top_order.push_back(u);
  74.  
  75.         // Iterate through all its neighbouring nodes
  76.         // of dequeued node u and decrease their in-degree
  77.         // by 1
  78.         list<int>::iterator itr;
  79.         for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
  80.  
  81.             // If in-degree becomes zero, add it to queue
  82.             if (--in_degree[*itr] == 0)
  83.             {
  84.               q.push(*itr);
  85.               //while we are pushing elements to the queue we will incrementing the cnt
  86.               cnt++;
  87.             } 
  88.  
  89.  
  90.     }
  91.  
  92.     // Check if there was a cycle
  93.     if (cnt != V) 
  94.         return true;
  95.     else
  96.         return false;
  97. }
  98.  
  99. // Driver program to test above functions
  100. int main()
  101. {
  102.     // Create a graph given in the above diagram
  103.     Graph g(6);
  104.     g.addEdge(5, 0);
  105.     g.addEdge(2, 1);
  106.     g.addEdge(0, 3);
  107.     g.addEdge(3, 2);
  108.     g.addEdge(5, 1);
  109.  
  110.     if (g.isCycle())
  111.         cout << "Yes";
  112.     else
  113.         cout << "No";
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/GsHna5
language:
C++ (gcc 8.3)
created:
2 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!