cycle detection in directed graph
//Cycle Detection in a directed graph using BFS ( Khan's Algorithm )
#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
}
bool isCyclic(vector<int>adj[],int n)
{
queue<int>q;
vector<int>vec(n,0);
for(int i=0;i<n;i++)
{
for(auto j:adj[i])
{
vec[j]++;
}
}
for(int i=0;i<n;i++)
{
if(vec[i]==0)
{
q.push(i);
}
}
int count=0;
while(!q.empty())
{
int val=q.front();
q.pop();
count++;
for(auto j:adj[val])
{
vec[j]--;
if(vec[j]==0)
{
q.push(j);
}
}
}
if(count==n)
{
return false;
}
return true;
}
int main()
{
int vertex,edges;
cout<<"Enter the number of vertex and edges:"<<endl;
cin>>vertex>>edges;
vector<int>adj[vertex];
int a,b;
cout<<"Enter the Links:"<<endl;
for(int i=0;i<vertex;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
if(isCyclic(adj,vertex))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}