hey everyone welcome back to the channel i hope you guys are doing extremely well so in this video we are going to learn about how to detect a cycle in a directed graph using this depth burst search algorithm now you know what is a directed graph when two nodes are connected by our directed edge so this is a particular directed graph now does this graph have a cycle is my question and the answer to that is yes you cannot call this a cycle no you cannot call this a cycle this is not a cycle because it is something like this and something like this like you're going like this and like this this is not a cycle but at the same time this is a cycle because this is going completely you started from here and you reached back here thereby we can say that this is a cycle so yes a cycle does exist and that is what you have to tell me so we have already solved how to detect a cycle in an undirected graph using the dfs algorithm but this is a directed graph now why will the same algorithm not work let's understand so i'll take this imagine you start the dfs call from one so you mark this as visited then you go to dfs call of two you mark this as visited now for two the adjacent neighbors is three so you will go uh the dfs to three so you'll go and mark it as visited from three you can go to four or you can go to seven so let's go to four so you go to four and you mark it as visited next from four you can go to five so you go to five and you mark it as visited from five you can only go to six so you go to six and you mark it as visited so beyond six can you go if i show you beyond six can you go no so you will come back from five can you go to seven no so you'll go back so apparently what will happen is you come back from six you come back from five you come back from four and you come back to three so the moment you come back to three three went to four to one of its adjacent notes and did the dfs now there is another adjacent node remaining seven so it will call a dfs for seven yes it will call a dfs for seven now what will happen is uh when it goes to seven it tends to mark it as visited it tends to mark it as visited but the next moment when you are standing at 7 it finds a nearby adjacent node which is already visited and thereby the same algorithm will say that this is a cycle because you know the logic if we visit an adjacent node which is not the parent if we visit the adjacent node which is not the parent and it is already visited we call that as a cycle we call that as a cycle this would have been true yes this would have been true if you did not have directed edges yes you would have edges like this this would have been true because you go here and then from this direction you go here so you meet since these are undirected edges you can say that this is a cycle but since over here we are dealing with something as directed edges thereby i cannot say something that you visited in this path and again if you visit in this path you cannot say that this is a complete cycle this is not a complete cycle thereby this visited algorithm using the dfs technique will fail yes thereby this visited algorithm using the dfs technique will pale so why did the technique fail because it was very simple you started from here then you went to here then you went to here then you went to here then you went to here then you went to here then you came back and then you took this path so it was a different path it was a different path in undirected it works because these are undirected edges so even if you go by this you can say this is a cycle indirected on that path you have to visit that same node again on that path like if you start from eight then you go then you go see on the path you visited eight again on the path you visited eight again but over here if you're going here you go but then the path comes back so that's not the same path so again you start a new path got it so on the same path very important line you'll understand when i do on the same path node has to be visited again then it is a cycle node has to be visited again then i can say that it is a cycle on the same path the node has to be visited again then only i can say that it has a cycle in order to solve this problem using dfs algorithm what i'll do is i'll draw this uh adjacency list for this particular graph and we will take two visited arrays one is the visited array itself and the other one is the path visited array now we see that we have 10 nodes let's uh take it off a 10 size so as of now our visited array is ready and the path visited array is ready as well so remember this we're going to do this as component wise because you know one can visit all of these guys but then this is kind of you have to again do a traversal so what we will always do is we will do it component of kind of stuff where we go from i to v 1 to v rather and we say if not visited of i then call the dfs to check if there is a cycle dfs of i if there is a cycle then you return true so a pretty simple code you have already learned this in component stuff so what is the first value of i one is that unvisited that is so what you'll do is you will start calling the dfs from one and what you will do is you will say hey one is visited and at the same time what you'll do is you'll say one is path visited as well what is path visit means it's being in the same path it's been on the same path okay so one is visited now who are the adjacent nodes of one let's quickly check it out it's two so what you'll do is you'll go to two at the same time you'll mark two as visited and path visited because it is in the same path now what the adjacent nodes of two it is three just three it is just three so you will go to now three you see two over here it is just having three so i'll go to three and you'll see that as visited and path visited very good next now you see three has two guys one is four one is seven again four and seven so first we will complete it for four then we will come back and complete it for seven so seven can wait let's complete it for four as of now so we will go to four and mark it as visited and path visited so visited and path visited marked right next what will happen is four will say i have five so we will go to now five and then mark five is visited and paths visited very important next five will say hey listen five i just have six so i'll say okay go to sex and please mark it as yes path visited and visited marked next six says i do not have any adjacent node six says i do not have any adjacent nodes so i'm like okay i'm done i'm done my journey is done so i will return and remember whenever you return you say that there has been no cycle so this guy will always return a false now what happens is when you go back from dfs of 6 when you go back from 6 you keep it as visited because you don't want to call a dfs again for six there is no point again calling for the dfs for six but you omit this six from your path visited yes you omit this six from a path visitor that means you make it zero again that means you make it zero again and now you go back now you are at five over so you omit this from path visited and make it zero again now you go back to four and you omit this from path visited now you go back to three three will not be omitted from path visited because because because it did a call for four but it still has a call for seven pending four is done seven is still remaining so what will happen is i will now go for seven now i'll see seven visit seven path visit okay so seven is done now seven checks who are my adjacent notes and seven says my adjacent node is five and now i see hey listen five is already visited five is already visited but wait this is zero it's not path visited it's not in the same path it's not in the same path it went in some other path but we don't care because we are not looking for something like this we're looking for a circle thereby it's in the new it's as of now the new path is this and five is not in the path so thereby i will not call it as a cycle i will not go beyond five that's why visit will help us i don't wanna again travel five i don't wanna gain travel six so that is where the visit will stop us and say hey listen seven do not go to dfs of five because we have already checked for five we have already checked for five by going to six as well we have already done that you don't need to do it again you just check hey five is visited but wait it's not visited in the same path thereby this is not a cycle so it now goes back now both of the call came back so this also now will say i did not find a cycle two will say i did not find the cycle one will say i did not find a cycle and everyone will go back and while going everyone will say we are done with the path yes we are done with the path so everyone will turn themselves to be zero everyone will turn themselves to be zero but the visited guys will be marked but the visited guys will be marked but the path visited guys will be turned to zero right so the dfs call is over yes the dfs call is over let's see raise it now what is the next thing so i will now become 2 now comes the twist whenever you see 2 you don't need to again do it you don't need to again do it you don't need to again do it there's no point in doing it this is where the visitor says hey i'm already visited don't do for me and it's not path visitors so it's fine it's but i've already gone through it and i did not find a cycle no need to do it same it'll be three three will be also like i'm already done i'll go on till eight because if you see from one to seven every one of them has been visited but we did not find a cycle so we do not go so the next one is eight the next one is eight the moment we have eight we say okay let's change the color visit it and path visit it so dfs of eight says visited and path visited so visited and parts visited now dfs of 8 says who am i adjacent dfs of 9. so i'm like ok nine visited and path visited nine visited and paths visited perfect next nine can go to the fs of 10 because for 9 10 is the addition it says visited and path visited visited and path visited that goes to 10. here comes the original gangster so whenever you add 10 you see eight as the adjacent node which is visited and path visited visited and path visited which means you started and you're on the path and you re-entered the same path because your path visited so thereby you say hey listen i got an eight which was visited and path visited so please return we have a cycle this line called dfs of trend and it got a true please return true this 8 called the 9 and got it true please return it true so ultimately this guy got it true thereby equal to equal to true so please return it true no further occurrence of 9 10 we don't need to check because we have returned a true that's how you check visited add a path visited and we just simply do a backtracking so as usual the c plus plus code is going to be on the right and the java code you can check it out on your left so we're given the adjacency list and the vector so we need a visited of the size by the way it's a zero based indexing so we can keep it something like this at the same time we need uh path visit right so we can keep it as zero-based perfect so we've taken visited and we have taken path visited now our task is to go from here to here and we say hey listen if this is not visited can you call the dfs check can you call the dfs check with this node probably we will need the adjacency we will need the visited and we'll need the path visited and if this eels are true it means there is a cycle and you return or else you can just go on checking at the end of the day if you did not find a cycle there is no cycle return or false now over here what you write is private boolean dfs check and you say okay this is my node let's see the adjacency vector of int adjacency let's take the visited i already visited let's see the path visited perfect and we say visited of node is equal to one we say path visited of node is equal to one and remember whenever we are going back at that time we need to make sure this guy is unmarked because the visiting has been done and we can return a false saying we did not find a stuff so this is the simple thing over here we traverse for adjacent notes it's over here we do our travels for our just sent notes so how do you translate notes very simple you say adjacency of node and you say okay listen if this guy is not visited just go and do a dfs for this guy with the adjacency with the visit and with the path visit perfect but if this dfs call that i made if this guy in the future goes across and finds a cycle if it finds a cycle then i am going to return it through if it doesn't then i'll just keep on going for the next adjacent node this is when the node is not visited now what if the node is visited if then it goes to an else and it goes to an else if the node if the node has been previously visited but it has to be visited on the same paths right it has to be visited on the same path so what do you do is you say okay listen if it has been visited but has it been path visited has it been visited in the same path if it has been feel free to return a true or else that's how you do it so this is how you do it and if you quickly run this off this will run fine remember if any of your calls says it has a cycle there's no need to check for further adjacent nodes there is absolutely no need to check for further adjacent nodes okay dfs was not declared oh my bad wtfast off check so you don't need to check for any further adjacent notes that is what you need to take care of also one more thing if it is path visited no need to do for any further just return false sorry return true and if after checking for all adjacent notes you did not find anything then you return or false right so this is how you can easily write it and if i ask you the time complexity of this particular code again we are plainly implementing a dfs algorithm so it's a dfs like b plus 2e that we generally take for undirected but this is a directed graph so you can call it as v plus e because every node will have a single edge so we can call it as v plus e as the time complexity and if i talk so what about the space complexity space complexity we can call it as 2n you might argue strive why we can't use a single visited array yes you can use it i'll give you that as a homework think on how can you use as a single visited array the hint is you can just mark visit as one and to mark path visit mark it as to so that's how you can use a single visited array as well i'll give you that as a homework if you are able to do it post the code in the comment section so that people can also figure that out i'll give you that as homework i've been teaching already a lot of things so guys i hope i was able to explain you this particular problem so just in case i was please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right away and if you haven't checked out our dp series and the hdc the links are in the description whenever this i'll be wrapping up this video let's meet in some other video till then bye bye take care whenever your heart is broken don't ever forget you're golden