title

G-19. Detect cycle in a directed graph using DFS | Java | C++

description

GfG-Problem Link: https://bit.ly/3QwPVsi
C++/Java/Codes and Notes Link: https://takeuforward.org/data-structure/detect-cycle-in-a-directed-graph-using-dfs-g-19/
DP Series: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
SDE Sheet: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
Check out our Website for curated resources: https://www.takeuforward.org/
Our Second Channel: https://www.youtube.com/channel/UCvEKHATlVq84hm1jduTYm8g
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: https://practice.geeksforgeeks.org/courses
Code "takeuforward" for 20% off on sys-design: https://get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: https://wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: https://indmoney.onelink.me/RmHC/idjex744
Earn 100 rs by making a Grow Account for investing: https://app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

detail

{'title': 'G-19. Detect cycle in a directed graph using DFS | Java | C++', 'heatmap': [{'end': 325.809, 'start': 268.442, 'weight': 0.829}, {'end': 355.081, 'start': 342.136, 'weight': 0.701}, {'end': 480.344, 'start': 455.442, 'weight': 0.863}, {'end': 575.8, 'start': 509.366, 'weight': 0.839}, {'end': 680.297, 'start': 649.059, 'weight': 0.736}, {'end': 921.159, 'start': 884.258, 'weight': 0.805}], 'summary': 'Covers detecting cycles in directed and undirected graphs using depth-first search (dfs) algorithm, graph traversal from nodes 1 to 6, and adjacency list and vector for dfs. it also discusses time and space complexity of dfs algorithm and the possibility of using a single visited array.', 'chapters': [{'end': 355.081, 'segs': [{'end': 32.549, 'src': 'embed', 'start': 3.305, 'weight': 0, 'content': [{'end': 4.786, 'text': 'hey, everyone, welcome back to the channel.', 'start': 3.305, 'duration': 1.481}, {'end': 6.748, 'text': 'i hope you guys are doing extremely well.', 'start': 4.786, 'duration': 1.962}, {'end': 15.296, 'text': 'so in this video we are going to learn about how to detect a cycle in a directed graph using this depth first search algorithm.', 'start': 6.748, 'duration': 8.548}, {'end': 19.88, 'text': 'now you know what is a directed graph when two nodes are connected by our directed edge.', 'start': 15.296, 'duration': 4.584}, {'end': 22.502, 'text': 'so this is a particular directed graph.', 'start': 19.88, 'duration': 2.622}, {'end': 30.969, 'text': 'now does this graph have a cycle, is my question, and the answer to that is yes, You cannot call this a cycle.', 'start': 22.502, 'duration': 8.467}, {'end': 32.549, 'text': 'No, you cannot call this a cycle.', 'start': 31.229, 'duration': 1.32}], 'summary': 'Teaching cycle detection in directed graph using dfs algorithm.', 'duration': 29.244, 'max_score': 3.305, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU3305.jpg'}, {'end': 75.293, 'src': 'embed', 'start': 45.1, 'weight': 1, 'content': [{'end': 47.162, 'text': 'You started from here and you reached back here.', 'start': 45.1, 'duration': 2.062}, {'end': 50.244, 'text': 'Thereby, we can say that this is a cycle.', 'start': 47.542, 'duration': 2.702}, {'end': 53.106, 'text': 'So, yes, a cycle does exist.', 'start': 50.644, 'duration': 2.462}, {'end': 54.628, 'text': 'And that is what you have to tell me.', 'start': 53.427, 'duration': 1.201}, {'end': 61.129, 'text': 'so we have already solved how to detect a cycle in an undirected graph using the dfs algorithm.', 'start': 55.268, 'duration': 5.861}, {'end': 63.15, 'text': 'but this is a directed graph.', 'start': 61.129, 'duration': 2.021}, {'end': 65.41, 'text': 'now why will the same algorithm not work?', 'start': 63.15, 'duration': 2.26}, {'end': 66.711, 'text': "let's understand.", 'start': 65.41, 'duration': 1.301}, {'end': 72.552, 'text': "so i'll take this imagine you start the dfs call from one, so you mark this as visited.", 'start': 66.711, 'duration': 5.841}, {'end': 75.293, 'text': 'then you go to dfs call of two.', 'start': 72.552, 'duration': 2.741}], 'summary': 'Detecting cycles in a directed graph using dfs algorithm.', 'duration': 30.193, 'max_score': 45.1, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU45100.jpg'}, {'end': 325.809, 'src': 'heatmap', 'start': 268.442, 'weight': 0.829, 'content': [{'end': 273.484, 'text': 'visited again, then i can say that it is a cycle on the same path.', 'start': 268.442, 'duration': 5.042}, {'end': 275.305, 'text': 'the node has to be visited again.', 'start': 273.484, 'duration': 1.821}, {'end': 278.106, 'text': 'then only i can say that it has a cycle.', 'start': 275.305, 'duration': 2.801}, {'end': 280.587, 'text': 'in order to solve this problem using dfs algorithm,', 'start': 278.106, 'duration': 2.481}, {'end': 287.55, 'text': "what i'll do is i'll draw this uh adjacency list for this particular graph and we will take two visited arrays.", 'start': 280.587, 'duration': 6.963}, {'end': 291.492, 'text': 'one is the visited array itself and the other one is the path visited array.', 'start': 287.55, 'duration': 3.942}, {'end': 293.913, 'text': 'now we see that we have 10 nodes.', 'start': 291.492, 'duration': 2.421}, {'end': 295.574, 'text': "let's take it of a 10 size.", 'start': 293.913, 'duration': 1.661}, {'end': 301.757, 'text': 'so as of now our visited array is ready and the path visited array is ready as well.', 'start': 296.354, 'duration': 5.403}, {'end': 304.078, 'text': 'so remember this.', 'start': 301.757, 'duration': 2.321}, {'end': 309.701, 'text': "we're going to do this as component wise, because you know one can visit all of these guys.", 'start': 304.078, 'duration': 5.623}, {'end': 313.483, 'text': 'but then this is kind of you have to again do a traversal.', 'start': 309.701, 'duration': 3.782}, {'end': 325.809, 'text': 'so what we will always do is we will do a component kind of stuff where we go from i to v, 1 to v rather, and we say if not visited of i,', 'start': 313.483, 'duration': 12.326}], 'summary': 'Using dfs algorithm to detect cycles in a graph with 10 nodes by maintaining two visited arrays.', 'duration': 57.367, 'max_score': 268.442, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU268442.jpg'}, {'end': 369.244, 'src': 'heatmap', 'start': 342.136, 'weight': 0.701, 'content': [{'end': 345.297, 'text': 'so what is the first value of i?', 'start': 342.136, 'duration': 3.161}, {'end': 347.198, 'text': 'one is that unvisited.', 'start': 345.297, 'duration': 1.901}, {'end': 348.118, 'text': 'that is so.', 'start': 347.198, 'duration': 0.92}, {'end': 355.081, 'text': 'what you will do is you will start calling the dfs from one and what you will do is you will say hey,', 'start': 348.118, 'duration': 6.963}, {'end': 360.422, 'text': "one is visited and at the same time what you'll do is you'll say one is path visited as well.", 'start': 355.081, 'duration': 5.341}, {'end': 361.022, 'text': 'what is path?', 'start': 360.422, 'duration': 0.6}, {'end': 363.383, 'text': "visit means it's being in the same path.", 'start': 361.022, 'duration': 2.361}, {'end': 364.543, 'text': "it's been on the same path.", 'start': 363.383, 'duration': 1.16}, {'end': 366.443, 'text': 'okay, so one is visited.', 'start': 364.543, 'duration': 1.9}, {'end': 368.104, 'text': 'now who are the adjacent nodes of one?', 'start': 366.443, 'duration': 1.661}, {'end': 369.244, 'text': "let's quickly check it out.", 'start': 368.104, 'duration': 1.14}], 'summary': 'Start dfs from node 1, mark as visited and explore adjacent nodes.', 'duration': 27.108, 'max_score': 342.136, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU342136.jpg'}], 'start': 3.305, 'title': 'Detecting cycle in directed graph', 'summary': 'Covers the process of detecting a cycle in a directed graph using the depth first search algorithm, highlighting the difference between directed and undirected graphs, and the key logic for identifying a cycle in a directed graph using dfs.', 'chapters': [{'end': 355.081, 'start': 3.305, 'title': 'Detecting cycle in directed graph', 'summary': 'Covers the process of detecting a cycle in a directed graph using the depth first search algorithm, highlighting the difference between directed and undirected graphs, and the key logic for identifying a cycle in a directed graph using dfs.', 'duration': 351.776, 'highlights': ['The chapter covers the process of detecting a cycle in a directed graph using the depth first search algorithm. The video tutorial focuses on using the depth first search algorithm to identify cycles within a directed graph.', 'Highlighting the difference between directed and undirected graphs. The tutorial emphasizes the difference in detecting cycles between directed and undirected graphs, explaining the specific challenges and logic involved.', 'Key logic for identifying a cycle in a directed graph using DFS. The tutorial explains the crucial logic for identifying cycles in directed graphs using DFS, emphasizing the importance of considering directed edges and revisited nodes on the same path.']}], 'duration': 351.776, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU3305.jpg', 'highlights': ['The tutorial emphasizes the difference in detecting cycles between directed and undirected graphs, explaining the specific challenges and logic involved.', 'The tutorial explains the crucial logic for identifying cycles in directed graphs using DFS, emphasizing the importance of considering directed edges and revisited nodes on the same path.', 'The video tutorial focuses on using the depth first search algorithm to identify cycles within a directed graph.']}, {'end': 750.107, 'segs': [{'end': 379.886, 'src': 'embed', 'start': 355.081, 'weight': 1, 'content': [{'end': 360.422, 'text': "one is visited and at the same time what you'll do is you'll say one is path visited as well.", 'start': 355.081, 'duration': 5.341}, {'end': 361.022, 'text': 'what is path?', 'start': 360.422, 'duration': 0.6}, {'end': 363.383, 'text': "visit means it's being in the same path.", 'start': 361.022, 'duration': 2.361}, {'end': 364.543, 'text': "it's been on the same path.", 'start': 363.383, 'duration': 1.16}, {'end': 366.443, 'text': 'okay, so one is visited.', 'start': 364.543, 'duration': 1.9}, {'end': 368.104, 'text': 'now who are the adjacent nodes of one?', 'start': 366.443, 'duration': 1.661}, {'end': 369.244, 'text': "let's quickly check it out.", 'start': 368.104, 'duration': 1.14}, {'end': 370.024, 'text': "it's two.", 'start': 369.244, 'duration': 0.78}, {'end': 373.165, 'text': "so what you'll do is you'll go to two at the same time.", 'start': 370.024, 'duration': 3.141}, {'end': 378.066, 'text': "you'll mark two as visited and path visited, because it is in the same path.", 'start': 373.165, 'duration': 4.901}, {'end': 379.886, 'text': 'now what the adjacent nodes of two.', 'start': 378.066, 'duration': 1.82}], 'summary': 'Nodes 1 and 2 are visited and marked as visited and path visited, as they are on the same path.', 'duration': 24.805, 'max_score': 355.081, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU355081.jpg'}, {'end': 450.278, 'src': 'embed', 'start': 421.566, 'weight': 0, 'content': [{'end': 424.487, 'text': 'I will mark 5 as visited and path visited.', 'start': 421.566, 'duration': 2.921}, {'end': 425.207, 'text': 'Very important.', 'start': 424.607, 'duration': 0.6}, {'end': 429.229, 'text': 'Next, 5 will say, hey, listen, 5, I just have 6.', 'start': 425.707, 'duration': 3.522}, {'end': 435.731, 'text': "So, I'll say, okay, go to 6 and please mark it as, yes, path visited and visited.", 'start': 429.229, 'duration': 6.502}, {'end': 440.492, 'text': 'Marked Next, 6 says, I do not have any adjacent node.', 'start': 436.171, 'duration': 4.321}, {'end': 443.193, 'text': '6 says, I do not have any adjacent nodes.', 'start': 440.512, 'duration': 2.681}, {'end': 444.874, 'text': "So, I'm like, okay, I'm done.", 'start': 443.533, 'duration': 1.341}, {'end': 445.634, 'text': "I'm done.", 'start': 445.354, 'duration': 0.28}, {'end': 450.278, 'text': 'my journey is done, so i will return and remember.', 'start': 446.394, 'duration': 3.884}], 'summary': 'Node 5 visited, then 6 visited and marked as path visited, 6 has no adjacent nodes.', 'duration': 28.712, 'max_score': 421.566, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU421566.jpg'}, {'end': 480.344, 'src': 'heatmap', 'start': 455.442, 'weight': 0.863, 'content': [{'end': 460.587, 'text': 'now what happens is when you go back from dfs of six, when you go back from six,', 'start': 455.442, 'duration': 5.145}, {'end': 464.491, 'text': "you keep it as visited because you don't want to call a dfs again for six.", 'start': 460.587, 'duration': 3.904}, {'end': 470.255, 'text': 'there is no point again calling for the dfs for six, but you omit the six from your path visited.', 'start': 464.491, 'duration': 5.764}, {'end': 472.277, 'text': 'yes, you omit this six from your path visitor.', 'start': 470.255, 'duration': 2.022}, {'end': 474.059, 'text': 'that means you make it zero again.', 'start': 472.277, 'duration': 1.782}, {'end': 477.421, 'text': 'that means you make it zero again and now you go back.', 'start': 474.059, 'duration': 3.362}, {'end': 480.344, 'text': 'now you are at five over.', 'start': 477.421, 'duration': 2.923}], 'summary': 'In dfs traversal, omit visited nodes to avoid redundant calls, maintaining path integrity.', 'duration': 24.902, 'max_score': 455.442, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU455442.jpg'}, {'end': 575.8, 'src': 'heatmap', 'start': 509.366, 'weight': 0.839, 'content': [{'end': 510.806, 'text': 'Now 7 checks.', 'start': 509.366, 'duration': 1.44}, {'end': 512.327, 'text': 'Who are my adjacent nodes.', 'start': 511.166, 'duration': 1.161}, {'end': 513.447, 'text': 'And 7 says.', 'start': 512.787, 'duration': 0.66}, {'end': 516.188, 'text': 'My adjacent node is 5.', 'start': 513.866, 'duration': 2.322}, {'end': 516.868, 'text': 'And now I see.', 'start': 516.188, 'duration': 0.68}, {'end': 517.548, 'text': 'Hey listen.', 'start': 517.087, 'duration': 0.461}, {'end': 519.948, 'text': '5 is already visited.', 'start': 517.568, 'duration': 2.38}, {'end': 522.51, 'text': '5 is already visited.', 'start': 519.969, 'duration': 2.541}, {'end': 523.21, 'text': 'But wait.', 'start': 522.87, 'duration': 0.34}, {'end': 525.472, 'text': 'this is zero.', 'start': 524.431, 'duration': 1.041}, {'end': 526.672, 'text': "it's not path visited.", 'start': 525.472, 'duration': 1.2}, {'end': 530.035, 'text': "it's not in the same path, it's not in the same path.", 'start': 526.672, 'duration': 3.363}, {'end': 531.636, 'text': 'it went in some other path.', 'start': 530.035, 'duration': 1.601}, {'end': 535.138, 'text': "but we don't care because we are not looking for something like this.", 'start': 531.636, 'duration': 3.502}, {'end': 538.88, 'text': "we're looking for a circle thereby.", 'start': 535.138, 'duration': 3.742}, {'end': 540.681, 'text': "it's in the new it's as of now.", 'start': 538.88, 'duration': 1.801}, {'end': 544.104, 'text': 'the new path is this and five is not in the path.', 'start': 540.681, 'duration': 3.423}, {'end': 546.085, 'text': 'so thereby i will not call it as a cycle.', 'start': 544.104, 'duration': 1.981}, {'end': 547.946, 'text': 'i will not go beyond five.', 'start': 546.425, 'duration': 1.521}, {'end': 549.306, 'text': "that's why visit will help us.", 'start': 547.946, 'duration': 1.36}, {'end': 552.847, 'text': "i don't want to again travel five, i don't want to again travel six.", 'start': 549.306, 'duration': 3.541}, {'end': 560.87, 'text': '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.', 'start': 552.847, 'duration': 8.023}, {'end': 564.011, 'text': 'we have already checked for five by going to six as well.', 'start': 560.87, 'duration': 3.141}, {'end': 565.252, 'text': 'we have already done that.', 'start': 564.011, 'duration': 1.241}, {'end': 567.512, 'text': "you don't need to do it again, you just check.", 'start': 565.252, 'duration': 2.26}, {'end': 571.394, 'text': "hey, five is visited, but wait, it's not visited in the same path thereby.", 'start': 567.512, 'duration': 3.882}, {'end': 572.234, 'text': 'this is not a cycle.', 'start': 571.394, 'duration': 0.84}, {'end': 573.997, 'text': 'so it now goes back.', 'start': 572.714, 'duration': 1.283}, {'end': 575.8, 'text': 'now both of the call came back.', 'start': 573.997, 'duration': 1.803}], 'summary': 'During the process, 7 checks its adjacent nodes, finding that 5 is not part of a cycle, stopping further traversal.', 'duration': 66.434, 'max_score': 509.366, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU509366.jpg'}, {'end': 680.297, 'src': 'heatmap', 'start': 649.059, 'weight': 0.736, 'content': [{'end': 656.543, 'text': "the moment we have eight, we say okay, let's change the color visited and path visited.", 'start': 649.059, 'duration': 7.484}, {'end': 659.985, 'text': 'so dfs of eight says visited and path visited.', 'start': 656.543, 'duration': 3.442}, {'end': 663.592, 'text': 'so visited and paths visited.', 'start': 659.985, 'duration': 3.607}, {'end': 667.574, 'text': 'now dfs of eight says who are my adjacent, dfs of nine.', 'start': 663.592, 'duration': 3.982}, {'end': 673.617, 'text': "so i'm like okay, nine visited and path visited, nine visited and path visited.", 'start': 667.574, 'duration': 6.043}, {'end': 680.297, 'text': 'perfect, next, 9 can go to dfs of 10, because for 9, 10 is the adjacent.', 'start': 673.617, 'duration': 6.68}], 'summary': 'Dfs algorithm explores 8, 9, and 10, updating their visited and path visited statuses.', 'duration': 31.238, 'max_score': 649.059, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU649059.jpg'}, {'end': 728.079, 'src': 'embed', 'start': 699.627, 'weight': 2, 'content': [{'end': 706.776, 'text': "which means you started and you're on the path and you re-entered the same path because your path visited.", 'start': 699.627, 'duration': 7.149}, {'end': 715.864, 'text': 'so thereby you say hey listen, i got an 8 which was visited and path visited.', 'start': 706.776, 'duration': 9.088}, {'end': 717.285, 'text': 'so please return.', 'start': 715.864, 'duration': 1.421}, {'end': 718.746, 'text': 'we have a cycle.', 'start': 717.285, 'duration': 1.461}, {'end': 722.249, 'text': 'this 9 called dfs of trend and it got a true.', 'start': 718.746, 'duration': 3.503}, {'end': 723.25, 'text': 'please return true.', 'start': 722.249, 'duration': 1.001}, {'end': 726.599, 'text': 'this 8 called a 9 and got a true.', 'start': 724.238, 'duration': 2.361}, {'end': 728.079, 'text': 'please return a true.', 'start': 726.599, 'duration': 1.48}], 'summary': 'Dfs algorithm identified 8 and 9, returning true.', 'duration': 28.452, 'max_score': 699.627, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU699627.jpg'}], 'start': 355.081, 'title': 'Graph traversal and detecting cycles', 'summary': 'Covers graph traversal algorithms, focusing on adjacent nodes and their traversal from nodes 1 to 6. it also explores detecting cycles in a graph using dfs and visited arrays, returning a true value if a cycle is detected.', 'chapters': [{'end': 450.278, 'start': 355.081, 'title': 'Graph traversal algorithm', 'summary': 'Explains the graph traversal algorithm by visiting and marking nodes as visited and path visited, with a focus on adjacent nodes and their traversal, covering nodes 1 to 6.', 'duration': 95.197, 'highlights': ['Node 6 has no adjacent nodes, concluding the traversal journey. Node 6 does not have any adjacent nodes, indicating the completion of the traversal journey.', 'Node 5 is marked as visited and path visited, signifying its traversal in the graph. Node 5 is visited and marked as path visited, emphasizing its traversal in the graph.', 'Node 4 is marked as visited and path visited, progressing the traversal. Node 4 is visited and marked as path visited, advancing the traversal process.']}, {'end': 750.107, 'start': 450.278, 'title': 'Detecting cycles in a graph', 'summary': 'Explains how to use the visited and path visited arrays to detect cycles in a graph using depth-first search (dfs), ensuring that the same node is not visited in the same path, ultimately returning a true value if a cycle is detected.', 'duration': 299.829, 'highlights': ['Using visited and path visited arrays to prevent revisiting nodes in the same path The technique of using the visited and path visited arrays ensures that nodes are not revisited in the same path during depth-first search (DFS), preventing the detection of cycles.', 'Returning true if a cycle is detected The algorithm returns a true value when a cycle is detected in the graph, facilitating the identification of cycles using the visited and path visited arrays.', 'Backtracking to check for cycles The process involves backtracking to check for cycles in the graph, using the visited and path visited arrays to ensure that the same node is not revisited in the same path during depth-first search (DFS).']}], 'duration': 395.026, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU355081.jpg', 'highlights': ['Node 6 has no adjacent nodes, concluding the traversal journey.', 'Using visited and path visited arrays to prevent revisiting nodes in the same path', 'Returning true if a cycle is detected']}, {'end': 1032.573, 'segs': [{'end': 779.528, 'src': 'embed', 'start': 750.107, 'weight': 2, 'content': [{'end': 753.189, 'text': "so we're given the adjacency list and the vector.", 'start': 750.107, 'duration': 3.082}, {'end': 755.73, 'text': 'so we need a visited of the size.', 'start': 753.189, 'duration': 2.541}, {'end': 759.271, 'text': "by the way, it's a zero based indexing, so we can keep it something like this.", 'start': 755.73, 'duration': 3.541}, {'end': 764.973, 'text': 'at the same time, we need a path visit right, so we can keep it as zero based.', 'start': 759.271, 'duration': 5.702}, {'end': 768.475, 'text': "perfect. so we've taken visited and we have taken path visited.", 'start': 764.973, 'duration': 3.502}, {'end': 771.096, 'text': 'now our task is to go from here to here.', 'start': 768.475, 'duration': 2.621}, {'end': 776.867, 'text': 'we say hey listen, if this is not visited, can you call the dfs check?', 'start': 772.285, 'duration': 4.582}, {'end': 779.528, 'text': 'can you call the dfs check with this node?', 'start': 776.867, 'duration': 2.661}], 'summary': 'Using adjacency list and vector, implement dfs to traverse nodes.', 'duration': 29.421, 'max_score': 750.107, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU750107.jpg'}, {'end': 820.35, 'src': 'embed', 'start': 789.032, 'weight': 0, 'content': [{'end': 792.994, 'text': 'at the end of the day you, if you did not find a cycle, there is no cycle, return a false.', 'start': 789.032, 'duration': 3.962}, {'end': 803.426, 'text': 'now over here what you write is private boolean dfs check and you say okay, this is my node.', 'start': 792.994, 'duration': 10.432}, {'end': 807.11, 'text': "let's take the adjacency vector of int adjacency.", 'start': 803.426, 'duration': 3.684}, {'end': 809.632, 'text': "let's take the visited int visited.", 'start': 807.11, 'duration': 2.522}, {'end': 811.734, 'text': "let's take the path visited.", 'start': 809.632, 'duration': 2.102}, {'end': 820.35, 'text': 'perfect. and we say visited of node is equal to one with a path visited of node is equal to one.', 'start': 811.734, 'duration': 8.616}], 'summary': 'The algorithm checks for cycles in a graph using a depth-first search approach.', 'duration': 31.318, 'max_score': 789.032, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU789032.jpg'}, {'end': 921.159, 'src': 'heatmap', 'start': 884.258, 'weight': 0.805, 'content': [{'end': 898.802, 'text': 'if the node has been previously visited but it has to be visited on the same path, right, it has to be visited on the same path.', 'start': 884.258, 'duration': 14.544}, {'end': 903.671, 'text': 'so what you do is you say okay, listen, if it has been visited, but has it been path visited?', 'start': 898.802, 'duration': 4.869}, {'end': 905.375, 'text': 'has it been visited on the same path?', 'start': 903.671, 'duration': 1.704}, {'end': 909.071, 'text': 'if it has been, feel free to return a truth, what else?', 'start': 905.375, 'duration': 3.696}, {'end': 910.331, 'text': "that's how you do it.", 'start': 909.071, 'duration': 1.26}, {'end': 915.275, 'text': 'so this is how you will do it, and if you quickly run this off, this will run fine.', 'start': 910.331, 'duration': 4.944}, {'end': 921.159, 'text': "remember, if any of your calls says it has a cycle, there's no need to check for further adjacent nodes.", 'start': 915.275, 'duration': 5.884}], 'summary': 'Check if node has been visited on the same path before returning truth.', 'duration': 36.901, 'max_score': 884.258, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU884258.jpg'}, {'end': 1010.851, 'src': 'embed', 'start': 955.844, 'weight': 1, 'content': [{'end': 960.808, 'text': "so it's a dfs like v plus 2e that we generally take for undirected.", 'start': 955.844, 'duration': 4.964}, {'end': 962.049, 'text': 'but this is a directed graph.', 'start': 960.808, 'duration': 1.241}, {'end': 967.332, 'text': 'so you can call it as v plus e, because every node will have a single edge.', 'start': 962.049, 'duration': 5.283}, {'end': 971.334, 'text': 'so you can call it as v plus e as the time complexity.', 'start': 967.332, 'duration': 4.002}, {'end': 974.556, 'text': 'and if i talk, so what about the space complexity, space complexity?', 'start': 971.334, 'duration': 3.222}, {'end': 976.497, 'text': 'we can call it as 2n.', 'start': 974.556, 'duration': 1.941}, {'end': 981.019, 'text': "you might argue, strive, why we can't use a single visited array.", 'start': 976.497, 'duration': 4.522}, {'end': 982.28, 'text': 'yes, you can use it.', 'start': 981.019, 'duration': 1.261}, {'end': 984.12, 'text': "i'll give you that as a homework.", 'start': 982.28, 'duration': 1.84}, {'end': 987.122, 'text': 'think on how can you use as a single visited array.', 'start': 984.12, 'duration': 3.002}, {'end': 998.501, 'text': 'the hint is you can just mark visit as one and to mark path, visit, mark it as two.', 'start': 987.122, 'duration': 11.379}, {'end': 1002.805, 'text': "so that's how you can use a single visited array as well.", 'start': 998.501, 'duration': 4.304}, {'end': 1004.746, 'text': "i'll give you that as a homework.", 'start': 1002.805, 'duration': 1.941}, {'end': 1010.851, 'text': 'uh, if you are able to do it, post the code in the comment section so that people can also figure that out.', 'start': 1004.746, 'duration': 6.105}], 'summary': 'For directed graph, time complexity is o(v + e), space complexity is 2n. consider using single visited array for optimization.', 'duration': 55.007, 'max_score': 955.844, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU955844.jpg'}], 'start': 750.107, 'title': 'Detecting cycles in a graph using dfs', 'summary': 'Explains the process of detecting cycles in a graph using depth-first search with adjacency list and vector, ensuring nodes are visited and marking the path visited, and returning true if a cycle is found; else, returning false. it also introduces the dfs algorithm, discussing its time complexity as v plus e and space complexity as 2n, while mentioning the possibility of using a single visited array.', 'chapters': [{'end': 915.275, 'start': 750.107, 'title': 'Detect cycle in graph', 'summary': 'Explains the process of detecting cycles in a graph using depth-first search (dfs) with adjacency list and vector, ensuring nodes are visited and marking the path visited, and returning true if a cycle is found; else, returning false.', 'duration': 165.168, 'highlights': ['The process involves using depth-first search (DFS) to check for cycles in a graph using adjacency list and vector, marking nodes as visited and path visited, and returning true if a cycle is found; else, returning false.', 'Nodes are marked as visited and path visited using arrays of the size of the graph, with zero-based indexing, to keep track of the visited nodes and those visited on the current path.', 'The algorithm checks if a node is visited and calls the DFS check with the node, adjacency, visited, and path visited arrays, returning true if a cycle is found; else, it continues checking.', 'Traversing adjacent nodes is done by iterating through the adjacency vector, calling the DFS for unvisited nodes, and returning true if a cycle is found during the traversal; else, it continues to the next adjacent node.']}, {'end': 1032.573, 'start': 915.275, 'title': 'Dfs algorithm time and space complexity', 'summary': 'Introduces the dfs algorithm, discussing its time complexity as v plus e and space complexity as 2n, while also mentioning the possibility of using a single visited array and urging viewers to consider it as homework.', 'duration': 117.298, 'highlights': ['DFS algorithm time complexity is v plus e for directed graph and v plus 2e for undirected graph.', 'Space complexity of the DFS algorithm is 2n.', 'A single visited array can be used by marking visit as one and path visit as two, which is provided as a homework task for the viewers.']}], 'duration': 282.466, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/9twcmtQj4DU/pics/9twcmtQj4DU750107.jpg', 'highlights': ['The process involves using depth-first search (DFS) to check for cycles in a graph using adjacency list and vector, marking nodes as visited and path visited, and returning true if a cycle is found; else, returning false.', 'DFS algorithm time complexity is v plus e for directed graph and v plus 2e for undirected graph.', 'Nodes are marked as visited and path visited using arrays of the size of the graph, with zero-based indexing, to keep track of the visited nodes and those visited on the current path.', 'Space complexity of the DFS algorithm is 2n.', 'A single visited array can be used by marking visit as one and path visit as two, which is provided as a homework task for the viewers.']}], 'highlights': ['The tutorial explains the crucial logic for identifying cycles in directed graphs using DFS, emphasizing the importance of considering directed edges and revisited nodes on the same path.', 'The process involves using depth-first search (DFS) to check for cycles in a graph using adjacency list and vector, marking nodes as visited and path visited, and returning true if a cycle is found; else, returning false.', 'The tutorial emphasizes the difference in detecting cycles between directed and undirected graphs, explaining the specific challenges and logic involved.', 'DFS algorithm time complexity is v plus e for directed graph and v plus 2e for undirected graph.', 'Using visited and path visited arrays to prevent revisiting nodes in the same path', 'A single visited array can be used by marking visit as one and path visit as two, which is provided as a homework task for the viewers.', 'Returning true if a cycle is detected', 'Nodes are marked as visited and path visited using arrays of the size of the graph, with zero-based indexing, to keep track of the visited nodes and those visited on the current path.', 'Space complexity of the DFS algorithm is 2n.', 'The video tutorial focuses on using the depth first search algorithm to identify cycles within a directed graph.', 'Node 6 has no adjacent nodes, concluding the traversal journey.']}