cycle detection in directed graph

Solutions on MaxInterview for cycle detection in directed graph by the best coders in the world

showing results for - "cycle detection in directed graph"
Zed
16 Jun 2018
1//Cycle Detection in a directed graph using BFS ( Khan's Algorithm )
2#include<bits/stdc++.h>
3using namespace std;
4void addedge(vector<int>adj[],int u,int v)
5{
6    adj[u].push_back(v);
7}
8bool isCyclic(vector<int>adj[],int n)
9{
10    queue<int>q;
11    vector<int>vec(n,0);
12    for(int i=0;i<n;i++)
13    {
14        for(auto j:adj[i])
15        {
16            vec[j]++;
17        }
18    }
19    for(int i=0;i<n;i++)
20    {
21        if(vec[i]==0)
22        {
23            q.push(i);
24        }
25    }
26    int count=0;
27    while(!q.empty())
28    {
29        int val=q.front();
30        q.pop();
31        count++;
32        for(auto j:adj[val])
33        {
34            vec[j]--;
35            if(vec[j]==0)
36            {
37                q.push(j);
38            }
39        }
40    }
41    if(count==n)
42    {
43        return false;
44    }
45  return true;
46}
47int main()
48{
49    int vertex,edges;
50    cout<<"Enter the number of vertex and edges:"<<endl;
51    cin>>vertex>>edges;
52    vector<int>adj[vertex];
53    int a,b;
54    cout<<"Enter the Links:"<<endl;
55    for(int i=0;i<vertex;i++)
56    {
57        cin>>a>>b;
58        addedge(adj,a,b);
59    }
60    if(isCyclic(adj,vertex))
61    {
62        cout<<"Yes"<<endl;
63    }
64    else
65    {
66        cout<<"No"<<endl;
67    }
68    return 0;
69}
70
71