Graph -14: Check if Directed Graph has Cycle (Using InDegree/BFS)

Solution:
- We'll achieve this via Indegree approach. We'll create hashmap, where key wil be index & value will be indegree for this index
- Now iterate the map & add all keys in queue for which indegree is 0
- Now poll the index form queue & get all children for this index, For each children decrease the indegree value by 1. Here if indegree becomes 0, add this in queue
- Every time you remove the item from queue, increase the visitedCount by 1
- Do this until queue is not empty
- At last if total nodes is not equal to visitedNodes, there exists a cycle in Graph

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[raghvendrakumarmishra]

Very good explanations. I prefer to change List<List<Integer>> graph ->> List[] adj and HashMap<Integer, Integer> incomingDegree ->> int[] incomingDegree where array size is number of vertices. I loved the explanation and code clarity/readability

[ClashWithSwap]

You're making graphs fun to understand. Thanks man keep it up 🔥

[sarveshchavan]

This code won't work if the graph is multicomponent !!

[PankajKumar-jldw]

Do not explain already written code. Write code and explain how things are there and why.

[suhail]

pls upload many graph problems and dp problems.

[coderbuddy]

Everything is alright but video is lengthy that's no problem but if it would short this will most rated channel for DS🙏

[crimsoncad]

It gave me some hard time for finding the cursor 😅

[adityarathod]

Hi, thanks for the video after watching your video i tried to implement it on interviewbit in C++, but some test care are giving run time error, can u plz take a look on my code(where is problem)

int Solution::solve(int n, vector<vector<int> > &prerequisites) {
vector<vector<int>> graph(n, vector<int>());
queue<int> q;
vector<int> in_degree(n, 0);
vector<int> ans;
//Making graph edge is unidirictional(p[1] --> p[0])
if(n!=prerequisites.size())
return 0;
for(auto p: prerequisites) {
graph[p[1]].push_back(p[0]);
++in_degree[p[0]]; // number of prerequites required
}
//Push all the elements in the queue which has 0 in_degree
for(int i=0;i<n;++i) {
if(in_degree[i]==0) {
q.push(i);
}
}
//if we remove the parent of a node then its in_degree will decreases by 1 unit
while(!q.empty()) {
int cur=q.front();
q.pop();
ans.push_back(cur);
for(int child: graph[cur]) { // adjacent
--in_degree[child]; // remove 1
if(in_degree[child]==0) { // no incoming
q.push(child);
}
}
}
return ans.size()!=n;
}