G-12. Detect a Cycle in an Undirected Graph using DFS | C++ | Java

Поделиться
HTML-код
  • Опубликовано: 24 дек 2024

Комментарии •

  • @takeUforward
    @takeUforward  2 года назад +85

    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

    • @darveshchhatani1411
      @darveshchhatani1411 2 года назад

      Please complete the series ASAP

    • @Sumeet_100
      @Sumeet_100 Год назад

      Hello bhaiya I have doubt that why the time complexity is O(N+2*E) why not O(2*E)

    • @tasneemayham974
      @tasneemayham974 10 месяцев назад

      @@Sumeet_100 Because you are going for all nodes N AND(+) visiting all degrees means 2E.

  • @dipaligangawane980
    @dipaligangawane980 2 года назад +36

    Really very good lecture series. Waiting for the next lectures.

  • @selva-qs9dw
    @selva-qs9dw 5 месяцев назад +5

    Without seeing a code i had doned
    Credits goes to striver who has an talent to make it as easy entire dsa for us....❤

  • @cinime
    @cinime 2 года назад +13

    Understood! So fantastic explanation as always, thank you very much!!

  • @harshvardhansingh2272
    @harshvardhansingh2272 2 года назад +12

    understood striver
    was able to do this by dfs by myself after watching and getting the concept from last video
    Amazing content as always

    • @prakhaxr
      @prakhaxr Год назад +8

      wah nanhe striver

    • @singhharsh8019
      @singhharsh8019 Год назад +1

      @@prakhaxr sure, I'll take it as a compliment🙂

  • @abhinavtomar8518
    @abhinavtomar8518 Год назад +7

    Amazing explanation bhaiya really amazing. Was trying to understand it from many source but was not able to understand properly. Really enjoy your teaching. Keep going bhaiya

  • @vikasbagri1225
    @vikasbagri1225 2 года назад +9

    understood it very well
    Your explanation is awesome

  • @rachitchaddha999
    @rachitchaddha999 Год назад +1

    Bhaiya ur teaching style is awesome.

  • @casinarro
    @casinarro 2 года назад +2

    It really feels good learning from you

  • @chandramoulipanyam5805
    @chandramoulipanyam5805 2 года назад

    Classic style of Explanation

  • @vikramragunathan6392
    @vikramragunathan6392 Год назад

    The way you explained. Just wow 😃😃

  • @mount2020
    @mount2020 Год назад

    kya hi hai bhai..u make to feel the concept..loving ur content so much

  • @anushravishankar9741
    @anushravishankar9741 Год назад +2

    Understanding more and more each day that I'm not smart enough to understand this high level logic
    Spent 1 year to understand, still haven't understood anything

    • @updownftw
      @updownftw 15 дней назад

      If you dont understand this, that means you need to first have sold understanding of Recursion, Linked List, and Tree problems. Once you get those, then only come to graphs. DONT GIVE UP

  • @anaghakr9900
    @anaghakr9900 Месяц назад

    Amazing explanation for DFS..

  • @anshusharma11
    @anshusharma11 Год назад +1

    Thanks for the wonderful explanation.

  • @KUMARSAURABH-s5i
    @KUMARSAURABH-s5i 7 месяцев назад

    Amazing session Understood!!

  • @VikasBagri-i5j
    @VikasBagri-i5j 5 месяцев назад

    understood, thanks for this amazing series

  • @vishankpathariya5926
    @vishankpathariya5926 5 месяцев назад

    great explanation bhaiya, totally understood

  • @hashcodez757
    @hashcodez757 4 месяца назад

    "UNDERSTOOD BHAIYA!!"

  • @rishabhgupta9846
    @rishabhgupta9846 2 года назад +1

    understood,great explanation

  • @tasneemayham974
    @tasneemayham974 10 месяцев назад

    PERFECTTTT STRIVERRR!!!!
    UNDERSTOOODDDD

  • @sripriyapotnuru5839
    @sripriyapotnuru5839 2 года назад

    Thank you, Striver 🙂

  • @muskangupta5873
    @muskangupta5873 7 месяцев назад

    got the intution because of your rotten oranges videos, i felt it is almost similar to that, thanks understood

  • @DevashishJose
    @DevashishJose 11 месяцев назад

    Understood, Thank you so much

  • @govindsharma7696
    @govindsharma7696 2 года назад

    Understood bhaiya 👍

  • @abhichi
    @abhichi 2 года назад

    Understood!!More!!✌🏻

  • @QnMisti
    @QnMisti 4 месяца назад

    understood Striver Bhaiya ❤❤

  • @supriyamanna715
    @supriyamanna715 2 года назад +1

    understood! Thanks man

  • @roshansah691
    @roshansah691 2 года назад

    Nice explanation, i understood 👍

  • @yashshukla1637
    @yashshukla1637 9 дней назад

    Thank you so much for the Video!!!!

  • @codeman3828
    @codeman3828 7 месяцев назад

    Thanks for the series

  • @nathonluke4058
    @nathonluke4058 2 года назад

    Loved it and understood

  • @jagratgupta8392
    @jagratgupta8392 Год назад +1

    understood sir very nice

  • @parshchoradia9909
    @parshchoradia9909 Год назад

    Understood Sir!

  • @harshwardhanpatki846
    @harshwardhanpatki846 Год назад

    Understood sir 🙇‍♂️

  • @codewithom11
    @codewithom11 Год назад

    Thank You So Much Sir😇

  • @UECAshutoshKumar
    @UECAshutoshKumar Год назад +1

    Thank you sir

  • @adebisisheriff159
    @adebisisheriff159 11 месяцев назад

    Amazing....... Always

  • @shubhankarmondal8690
    @shubhankarmondal8690 2 года назад

    Understood 🙌🔥

  • @sanketmudholkar2889
    @sanketmudholkar2889 2 года назад

    Bold me "UNDERSTOOD"

  • @fadebeyond
    @fadebeyond 2 года назад

    Understood Bhaiya.

  • @utkarshpatidar167
    @utkarshpatidar167 Год назад

    Understood 🙌🏻

  • @AgrimArtofficial
    @AgrimArtofficial 8 месяцев назад

    This question can also be done by using the concept V=E+1 in cyclic undirected graph using dfs

  • @debanjan10
    @debanjan10 Год назад +1

    understood sir

  • @vaibhavchauhan1930
    @vaibhavchauhan1930 2 года назад

    understood, Thank you so much

  • @adityasaxena6971
    @adityasaxena6971 Год назад

    Understood💯

  • @atharvadeshmukh6328
    @atharvadeshmukh6328 10 месяцев назад

    Understood 😄

  • @aparna5364
    @aparna5364 2 года назад

    Understood 🎊

  • @DivineVision201
    @DivineVision201 2 года назад +2

    understood bhaiya. Are there more videos coming for Graph in this playlist? It would be very helpful if there are more to come..
    But great work..

  • @mriduljain6809
    @mriduljain6809 Год назад

    Understood Bhaiya

  • @coolgaurav5163
    @coolgaurav5163 4 месяца назад

    Understoood

  • @ANURAGSINGH-nl2ll
    @ANURAGSINGH-nl2ll Год назад

    understood thank you

  • @yashgupta6797
    @yashgupta6797 2 года назад

    understood sir!

  • @fmkhandwala39
    @fmkhandwala39 2 года назад

    UNDERSTOOD!

  • @DeadPoolx1712
    @DeadPoolx1712 25 дней назад

    UNDERSTOOD;

  • @RVcalisthenics
    @RVcalisthenics 3 месяца назад

    understood striver

  • @them.pranay7196
    @them.pranay7196 4 месяца назад

    super duper hit video

  • @Learnprogramming-q7f
    @Learnprogramming-q7f 8 месяцев назад

    thank you Bhaiya

  • @tahmidulislamomi1398
    @tahmidulislamomi1398 Год назад

    Superb

  • @utsavkumar6048
    @utsavkumar6048 2 года назад

    understood sirji

  • @TravelTracksByDebo
    @TravelTracksByDebo 2 года назад

    understood bhaiya

  • @ritikkoshta5792
    @ritikkoshta5792 Год назад

    understood 😁😁

  • @Desi_Debugger
    @Desi_Debugger 2 года назад

    bhaiya ji maja agaya

  • @jaishriharivishnu
    @jaishriharivishnu 6 месяцев назад

    the concept of more than two parent to detect cycle is also good......
    If in any adjacency list, if we find two or more visited node during BFS or DFS in a undirected graph then it will have a cycle.
    bool detectcycle(int i, vector&vis, vectoradj[]){
    bool iscycledetected=false;
    vis[i]=1;
    int count=0;
    for(auto K:adj[i]){
    if(vis[K])count++;
    }
    if(count>1)iscycledetected=true;// this is the check for cycle

    for(auto K:adj[i]){
    if(!vis[K]){
    bool x1=detectcycle(K,vis,adj);
    iscycledetected=x1|iscycledetected;
    }
    }
    return iscycledetected;
    }

    bool isCycle(int V, vector adj[]) {
    // This is the main function
    vectorvis(V);
    for(int i=0; i

  • @SatyamKumar-bw4vi
    @SatyamKumar-bw4vi 2 года назад +1

    Hare Krishna.! Great Video

  • @prajwalhorti3717
    @prajwalhorti3717 2 года назад

    understood!

  • @ashishbhardwaj4334
    @ashishbhardwaj4334 Год назад

    UNDERSTOOD

  • @subhadeepghosh2813
    @subhadeepghosh2813 2 года назад

    plz make a video on snake and ladder.love u bro

  • @cypher7536
    @cypher7536 2 года назад

    Understood!

  • @-Corvo_Attano
    @-Corvo_Attano 2 года назад +1

    understood :)

  • @sypher4735
    @sypher4735 2 года назад

    understood.

  • @iDepth
    @iDepth 2 года назад

    Understood

  • @kritisingh3194
    @kritisingh3194 2 года назад

    Understood. :)

  • @Dadycalling55
    @Dadycalling55 2 года назад

    understood

  • @kholiyamails1257
    @kholiyamails1257 2 года назад

    thanks thanks thanks 😅

  • @Simran_048
    @Simran_048 5 месяцев назад +1

    Simple intution is : It's not the parent still already visited that means cycle exists

  • @Niki_0011
    @Niki_0011 8 месяцев назад

    Understood ++

  • @Joy-b6r
    @Joy-b6r 7 месяцев назад +1

    Isn't the both conditions are same inside the loop why we need if condition inside if pls explain...,

  • @isheep9025
    @isheep9025 Год назад +2

    Using non recursive DFS:
    class Solution {
    public:
    bool solver(int V,vector & visited,vector adj[],int child,int parent) {

    stack st;
    st.push({child,parent});

    while(!st.empty())
    {
    auto p=st.top();
    int child=p.first;
    int parent=p.second;
    st.pop();
    if(visited[child]==false)
    visited[child]=true;

    for(int ele:adj[child])
    {
    if(!visited[ele])
    {
    st.push({ele,child});
    }

    else if(ele!=parent)
    return true;
    }
    }

    return false;

    }
    public:
    // Function to detect cycle in an undirected graph.
    bool isCycle(int V, vector adj[]) {

    vector visited(V,0);

    for(int i=0;i

  • @VEDANSHSHARMA-o6k
    @VEDANSHSHARMA-o6k 2 месяца назад

    ur awesome

  • @gururajsavalgi4496
    @gururajsavalgi4496 4 месяца назад

    nice

  • @pratapsingh9638
    @pratapsingh9638 2 года назад

    striver please make videos on topic like segment tree

  • @AjayYadav-xi9sj
    @AjayYadav-xi9sj 2 года назад +1

    When is the possible date of completion of the series.

  • @fairoossahfeerulwasihf1139
    @fairoossahfeerulwasihf1139 3 месяца назад

    will it work fine even for this case where 2 nodes are there each points each other ond forming cycle?

  • @shivanshsingh176
    @shivanshsingh176 2 года назад +3

    Instead of "if(dfs(adjacentNode, node, visited, adj) == true)
    return true; ", if we directly return the dfs function, then it is incorrect. Whu so ?
    I think It should be same

    • @devanshchauhan7065
      @devanshchauhan7065 2 года назад +2

      ya exactly, same doubt, can someone explain please!

    • @gautamsingh2599
      @gautamsingh2599 Год назад

      in the above statement it the output of the function is true it will directly return it and if you return at last it may or may not return true always

    • @Jaydeeeeeeep
      @Jaydeeeeeeep Год назад

      Because detect function will return true or false for every component between one to n,
      Lets say first component has no cycle, but second one has a cycle.
      But according to your code, it will not go to second component, it will just return false after iterating in first component.
      So, if detect function sends a true, then only you should return true, else nothing

    • @vijaymehrotra3236
      @vijaymehrotra3236 Год назад

      in directly returning it will always return something
      but in correct method shone in video it will only return true if the dfs function is true

  • @anonymousboy2868
    @anonymousboy2868 5 месяцев назад

    understooddd

  • @abhinavanand1904
    @abhinavanand1904 Год назад

    Can anyone tell me that why striver has used a vector of array for the visited array instead of a single vector/array in C++ code, or its just mistyped while coding ??

  • @anuraggulati2167
    @anuraggulati2167 2 года назад

    uinderstood bhaiya

  • @sumeetubale3923
    @sumeetubale3923 Год назад +2

    why the time complexity is O(N+ 2*E) instead of that why not O(2*E) ??

    • @gouravchaki7990
      @gouravchaki7990 Год назад

      Cuz a loop runs from 1->n to check whether node is visited or not, if not visited the dfs is performed.

  • @aniket6676
    @aniket6676 2 года назад +4

    Hey Striver,
    I had a doubt, why do we need to store the parent of each node?
    Can't we just count the number of neighboring nodes, of a particular node, that are visited,
    if the count is more than 1, for any node, then we can conclude that the cycle is present?
    Plz let me know if I am missing out on something in my approach.
    Following is the implementation for the above logic:
    bool detectDfs(int start, vector adj[], int vis[]){
    vis[start] = 1;
    int visCnt = 0;
    bool flag = false;
    for(auto it : adj[start]){
    if(++visCnt > 1) flag = true;
    else if(!vis[it]){
    flag = flag || detectDfs(it, adj, vis);
    }
    if(flag == true) return flag;
    }
    return flag;
    }
    bool isCycle(int V, vector adj[]) {
    // Code here
    int vis[V] = {0};
    for(int i = 0; i < V; i++){
    if(!vis[i] && detectDfs(i, adj, vis)) return true;
    }
    return false;
    }

    • @kanishkraj5640
      @kanishkraj5640 2 года назад

      No..There is possibility when there are more than one visited and the graph will not contain cycle...Refer GFG Article for such example.

    • @sviswesh3555
      @sviswesh3555 2 года назад

      @@kanishkraj5640 I understood @Aniket 's qn but couldn't understand your answer. How can a node be visited, not be the parent, and yet no cycle is formed?

    • @shripandey4120
      @shripandey4120 2 года назад

      I think, you are right.

    • @illusionhex1200
      @illusionhex1200 2 года назад

      In this example you can visit back to the parent node if not stored them.
      1 ( 2 3)
      2 (1 3)
      Here you will go to 2 from 1 and again 1 from 2 and you got your cycle when there is no cycle at all.

    • @arindammandal1513
      @arindammandal1513 2 года назад

      No, if u have a graph with one node and 3 outwards edge , then it doesnt mean its a cycle right?
      like 1--->2,3,4
      so u visit 2,3 from 1 and visit counts become 2 > 1 , does that mean it has a cycle? No

  • @addityasharma6426
    @addityasharma6426 2 года назад

    understood :-)

  • @artifice_abhi
    @artifice_abhi 2 года назад +1

    understood++;

  • @Anony.musk01
    @Anony.musk01 Год назад

    one doubt, why do you write functions under private? any specific reason for that?

    • @omkarshendge5438
      @omkarshendge5438 Год назад +1

      you dont want that function to be exposed somewhere else! you specifically want dfs or dfs for this solution class only and other classes if made can have their methods likewise.
      yes u can add the function under public too not an issue but as far as clean code is concerned its better to add under private
      "Methods that serve as the inner workings of your class and don’t output or display information." read this carefully for private

  • @ayushgarg9099
    @ayushgarg9099 Год назад

    A simple question if anyone can help me understand!
    If we are given a source node and we are performing DFS on a connected undirected graph(i.e. a single component), how is the time complexity O(N+2E), shoudn't it be just O(2E) which is summation of degrees?

    • @aprajitakumari3745
      @aprajitakumari3745 Год назад

      For N nodes we are traversing in the wrost case

    • @anshumaan1024
      @anshumaan1024 Год назад +1

      @@aprajitakumari3745 because for every node, we are traversing all its adjacent nodes

    • @reee896
      @reee896 Год назад

      So In the worst case the 2E will not be done cause worst case means every will be a component in itself

  • @kushagramishra3026
    @kushagramishra3026 2 года назад +2

    "Understood"

  • @himanshugupta-mz2yk
    @himanshugupta-mz2yk Год назад

    Bhaiya Python code in coding ninja is not accepted but code of other languages are accepted

  • @kushalchakraborty6970
    @kushalchakraborty6970 2 года назад +20

    If possible bring 2-3 videos per day

    • @bruvhellnah
      @bruvhellnah 2 года назад +61

      Might as well ask him to leave his full time job for your convenience.

    • @kushalchakraborty6970
      @kushalchakraborty6970 2 года назад

      @@bruvhellnah gand mara , tere se Bola hai Kuch? English aata hai ?? Nhi aata toh juss go n check the meaning of if possible ,

    • @udaypratapsingh8923
      @udaypratapsingh8923 2 года назад +15

      @@bruvhellnah destroy in second 🤣🤣🤣🤣🤣🤣🤣🤣

    • @MindMunchies.
      @MindMunchies. Год назад

      @@bruvhellnah 😂😂😂

    • @yeswanthh5068
      @yeswanthh5068 Год назад

      🙄🙏

  • @Yash-uk8ib
    @Yash-uk8ib 2 года назад +3

    Sir, a small doubt?
    Lets say the for loop calls dfs fn X times where X

    • @sumerrawat6947
      @sumerrawat6947 2 года назад +2

      X + O(N+2E) hoga bro , and X

    • @Yash-uk8ib
      @Yash-uk8ib 2 года назад +1

      @@sumerrawat6947 thanks sir!!
      Pr ek baat or btadijiye
      Aap bol rhe ho ki har component ki complexity addup hui hai
      To sir is hisab se complexity
      O(c1+2e1) + O(c2+2e2) ..... O(x+2ex ) honi chiye thi?
      Agr yhi hai to kya ye eqn hi X + O(N+2E) ke equal hai?

    • @sumerrawat6947
      @sumerrawat6947 2 года назад +5

      @@Yash-uk8ib dekh bhai
      Lets say we have 4 connected components
      so total 4 calls will be made
      complexity of each component
      for iteration 1:
      O(N1+2E1)
      for iteration 2:
      O(N2+2E2)
      for iteration 3
      O(N3+2E3)
      for iteration 4
      O(N4+2E4)
      as the number of nodes are different in each componenet
      total TIME COMPLEXITY =
      4 + O(N1+N2+N3+N4) + 2(E1+E2+E3+E4)
      = 4+O(N + 2E )
      or
      X + O(N+2E)
      where X is the total number of calls
      N is total number of nodes in WHOLE GRAPH
      E is total edges in WHOLE GRAPH

    • @MdSarfrazcs
      @MdSarfrazcs 2 года назад

      @@sumerrawat6947 can you suggest a playlist for time complexity of recursion and graph .

  • @brahmkaransingh8804
    @brahmkaransingh8804 2 года назад

    UnderStood

  • @DilpreetSingh-cs7yz
    @DilpreetSingh-cs7yz 2 года назад +2

    Why writing the fucntion in private ?