G-11. Detect a Cycle in an Undirected Graph using BFS | C++ | Java

GfG-Problem Link: bit.ly/3cZMJXp
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79

[@aeroabrar_31]

@takeUforward
Please use Queue as a horizontal data structure , being confused as like stack..

[@rex027zz]

understood

[@tasneemayham974]

@@aeroabrar_31 No I think if he started using horizontal data structure we will get confused because we are used to drawing it out like that from all previous lectures and series!

[@rajneeshdubey5779]

We can also solve it without storing the parent , A particular node can be marked visited only by its parent so when we reach a node and traverse all its adjacent node and find more than one visited ,that shows this node has more than one parent or we can simply say this particular node is also getting visited from another direction and in that case we can say there is cycle presert .
class Solution {
public:
// Function to detect cycle in an undirected graph.
bool bfs(int node,vector &vis, vector adj[]){
queue q;
q.push(node);
vis[node]=1;
while(!q.empty()){
int frnt= q.front();
q.pop();
int cnt=0;
for(auto it:adj[frnt]){
if(!vis[it]){
q.push(it);
vis[it]=1;
}
else {
cnt++;
}
}
if(cnt>1) return true;
}
return false;
}
bool isCycle(int V, vector adj[]) {
// Code here
vector vis(V,0);
for(int i=0;i

[@AbhishekKumar-yv6ih]

Nice Idea: since there can only be one parent. If 'else' part runs more than once, it means there is a cycle.

[@IshaanJoshi-ms9mb]

thanks for sharing this alternative, its always good to know more than one way to solve a problem.

[@jaishriharivishnu]

nice

[@gautamgupta7148]

I still don't get it how. How will you know parent is visiting that node. If graph is like 1 then 2 3 and then 4 5 connected respectively then if we are at 4 then 2 is already visited. and then it will go in else case will do ++ and after that return true

[@jaishriharivishnu]

@@gautamgupta7148 can't explain properly here.... But while iterating in the adj list... If there are more than two visited nodes, then it will have cycle..... This is same concept as described by the guy above

[@iflifewasmovie4766]

Thank you for this series and seriously this series is much much finer than the previous one!! Thank you.

[@The_Shubham_Soni]

People told me that graph is a hard topic and many people failed to do so, but Striver's Graph series is just Amazing it looks quite easy for me. ♥

[@tasneemayham974]

I look at the comments in LeetCode's Discussion tab when they talk about DP and I go like: why the hell is everybody scared of DP. It's not that hard.
ONLY HAPPENS WHEN YOU LEARN FROM STRIVERRR1!!!!!!!

[@dhruvbajaj5079]

This is coder's gold mine. Thank you for such great explanations.

[@sbrosgamerz3470]

This Guy is like the greatest teacher for any student......Great Work Guruji 😉☺️

[@DhanushS-we6ql]

finally understood after 1 hour ..thanks

[@GAMIX7]

Hey Striver, amazing video, there's one suggestion: You don't need to loop once in boolean array, as in Java the values are false by default, same for int[] array its filled with 0 initially,
Well, in DP I use Arrays.fill(arr, -1); //Internally this method runs a loop and saves much code space.
Edit: we can also use if( !vis[i] ) //this will check if it is false or not, to check if the node is already visited or not!
Love your videos! Thanks

[@takeUforward]

Thanks, I was googling and writing java code. Will keep this in mind.

[@lavanyam3224]

11:50 Wow the climax of the movie!! Amazing explanation striver. Thankyou :)

[@iamnoob7593]

Just came for revision , Man u r a legend So amazing explanation.

[@ajazahmed5079]

really great explanations covering all the edge cases and imp. small concepts in depth. You are really great bhaiya!

[@tasneemayham974]

11:52 Bro! It seems like someone stole ur child! LOLLLL!! Only Striver can have that much fun and enthusiasm in a lesson!! Thank youuu sir for making us smile and learn at the same time!!!

[@kanishkpandey6427]

3 saal graph aadha adhura padha...ab raj baba ki kripa h ki roz ek video dekh ke confidence aa jata h XD

[@stith_pragya]

Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@surojitsantra7627]

If for a node, any 2 connected nodes are already visited then we can say it is cycle. Because one of them will be parent and other one is already visited by some other node.
For example, 2->3,4,5
Let say 3 and 4 already visited then one of them must be parent and other one is visited by some other node.
In that way we xan avoid to store the parent info in the queue.

[@bhavkushwaha]

Thankyou Striver, Understood!

[@beginnertopro7265]

Bhaiya your teaching style is awesome 🔥🔥🔥🔥🔥🔥🔥,
No Any youtuber can explain like u 😊😊

[@beinghappy9223]

Best explanation on Detecting Cycle Using BFS

[@cinime]

Understood! Awesome explanation as always, thank you so much!!

[@umeshkaushik710]

Awesome explanation bhaiya. You inspire us a lot. Hope to meet you someday.😇😇

[@CellerCity]

Thanks! I was stuck at this problem for too long.

[@hareshnayak7302]

Understood, ea pura wow wala solution 😄.

[@harshitsamdhani2426]

understood repeating is helpful and overall explanation is best that I could find in youtube

[@abhijeetkumar2970]

understood

[@atharvadeshmukh6328]

Understood, thanks!

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@morganyu3391]

Understood bhaiya!

[@vishalharne7674]

you are just amazing bro i had watched babbar DSA 90 videos i do tell you that you have very nice skill of teaching i am not comparing but ya you are like
suryakumar yadav
kam me jyada ka maja
to the point straight to the concept

[@anjani-d6p]

keep up the good work

[@RohitKumar-dz8dh]

Understood 😊

[@randomvariate21]

very well
understood

[@DevashishJose]

Understood, Thank you so much.

[@it_08amanagarwal35]

Excellent Lecture bro ❤❤❤❤❤

[@rudranshagg2580]

Doubt in TC:
We are not multiplying and are only adding the TC O(V) for looping on the visited vector , reason given by striver for that is because
we are not going to call that for each node as most nodes will be visited when starting from a node , but my doubt is still hum call toh number of
nodes ke liye hi krenge na vis vector vale loop mein voh alag baat h ki dfs() function call kis kis ke liye hoga 🤷‼

[@arunmahajan1028]

11:57
🥶

[@abhinavkumar6584]

understood. PS: I guess there wasn't any need to pass V in bfs function

[@impatientgaming9868]

really good explanation and visualization.

[@LearnerForever123]

Understood

[@UECAshutoshKumar]

Thank you sir

[@sanketatmaram]

understood!

[@codeman3828]

Awesome explanation

[@AbdulKadir-bh3el]

You are just amazing!!!, Plz keep uploading such a premium content.

[@sachinvarma9949]

god of coding for me

[@Niki_0011]

Understood ❤❤❤

[@mdsameer533]

understood sir !

[@nathonluke4058]

Understood.....🔥

[@_hulk748]

Thankyou sir understood🙏❤🙇‍♂

[@harshvardhansingh2272]

understood striver
great explanation

[@shrutyshruty7669]

Understood
Can you please tell till when will you upload all the remaining videos.

[@ishangujarathi10]

amazing intuition as always!!!tysm

[@bhuvneshwargarg93]

Hi Striver, Great explanation. I have one query and i.e. To solve any problem if we are using queue, in that case do we need to use queue with array or queue with linked list? Specially when programming with javascript. Thanks.

[@KartikeyTT]

tysm sir

[@akashjha822]

Understood striver ❤️

[@introvert3487]

Extremely well as always

[@khushikalra9846]

please make playlists for string as well

[@javierdavidhernandezestrad7334]

Thanks, understood

[@jatilyadav4000]

understood.. Thank you soo much

[@adebisisheriff159]

Thanks Striver

[@pratikshadhole6694]

perfect

[@user-ci6dd9wl6l]

1- remove from the graph the nodes that have less than 2 connections
2- count the connections
3- count the nodes
4 - if the connections are equals or more than the nodes you have a cycle
how is this method called?🙃

[@potassium_cyanide_boy8515]

bhai gusse me bhi arre the lagra beech beech me

[@parshchoradia9909]

Understood Sir!

[@suheabkhan2546]

understood very well 💖

[@vikasbagri1225]

understood it very well

[@studynewthings1727]

Understood.

[@AJ-xc3ks]

Outstanding..

[@riddhibandyopadhyay584]

Understood!!!! :D

[@Kaurs_Life]

Million Thanks

[@harshdasila6680]

understooodddd

[@ANURAGSINGH-nl2ll]

understood thank you

[@manavnaharwal1921]

Understood! 🙌

[@gautamsaxena4647]

understood bhaiya

[@sumitworld918]

Understood 😃

[@rajpattern]

Am I the only one who doesn't understand why he uses the + sign instead of the * sign in time complexity?? Please help if you understand!

[@aniketgupta8064]

Yes I think you're the only one.

[@aditiagarwal3222]

hiii.. will this logic still work if there are only 2 nodes in the graph and a cycle exists between them such that 0->1 and 1->0? because in that case the iterator will always be equals to parent??

[@SHRUGX_YT]

I too have the same doubt! please comment if you get the answer elsewhere.

[@adityamohite9023]

This is an undirected graph thus the condition u mentioned will always be true for all the edges . Hence we have to detect the cycle in the graph as a whole with undirected edges which will always be formed with 3 or more edges.

[@aditiagarwal3222]

Alright thank you

[@nipunrawat7137]

i guess that cannot be considered as a cycle.

[@Learnprogramming-q7f]

thank you bhaiya

[@AbhishekKumar-xi6jd]

Noted ✌🏼

[@mriduljain6809]

Understood Bhaiya

[@gokulakrishnan5096]

Thanks for the lecture. Just a quick question, if there is a time limitation, is there any difference if I just do the older graph series? What would you recommend? ( I have only 1-2 weeks remaining)

[@takeUforward]

Yes you can, just check the problems that I add here

[@gokulakrishnan5096]

@@takeUforward thanks a lot for the quick response!

[@suryakiran2970]

UnderStood❤

[@ganeshmula4508]

understood sir🙏

[@venutalla5932]

UNDERSTOOD

[@Sarkar.editsz]

Thanks a lot bhaiya

[@anirudhrajput8282]

u should clearly tell about the variable u declare like node and parent so plz regard over this

[@rishabhagarwal8049]

Understood sir

[@akashsahu2571]

yes

[@manasranjanmahapatra3729]

Understood!

[@mriduljain1981]

understood.

[@rupalitiwari5012]

Hi, Why are you making another video on the same topic that you already covered 1 year ago, which one should we choose to watch?

[@shubhambhatt2704]

12:01 can anyone please help me with that logic?
I dont get what he is trying to say there

[@no_name45689]

Well, Parent here means the previous node. And suppose, if next node is already visited but it is not previous node then it means, cycle exist.

[@mirdulswarup9065]

can someone tell me why the visited array is not being passed as reference ?

[@visheshkaran7083]

Because in c++ arrays are already passed as reference you don't need to write &

[@soumya1713]

Waiting for your surprise #independentWithStiver.

[@areebahmadsiddiqui2648]

So am I

[@dipendersingh1536]

It’s delayed check linkedin

[@ishanupadhyay5351]

Sir, why the visited array is not passed by reference in the function?

[@backbencher1209]

because array is already passed by reference .

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@amangaur4231]

Understooood

[@adityasaxena6971]

Understood💯💯💯

[@suhaanbhandary4009]

understood!!

[@karanveersharma4643]

am i the only one who isn't able to understand the formate in which input are supplied in the question?

[@MARK-hw8jm]

Why not dfs??

[@kritisingh3194]

Understood. :)