Detect cycle in a Directed Graph | Using DFS | Graph Data Structure | DSA-One Course #78

Hey guys, In this video, We're going to solve an interesting problem in Graphs known as Detect Cycle in a Directed Graph.
Pre-requisites:
DFS Video: • DFS Algorithm | Depth ...
Detect cycle in an Undirected Graph: • Detect Cycle in Undire...
Practice here: practice.geeks...
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
🥳 Join our Telegram Community:
Telegram channel: telegram.me/re...
Telegram group: telegram.me/ds...
🚀 Follow me on:
Instagram: / anuj.kumar.sharma
Linkedin: / sharma-kumar-anuj
Twitter: / realanujbhaiya
📚 Complete DSA Playlist: • DSA-One Course - The C...
Complete Android Development Playlist: • Android Development Tu...
Hashtags:
#anujbhaiya #dsaone
Tags:
detect cycle in a directed graph
detect cycle in directed graph
cycle in directed graph
anuj bhaiya
cycle detection in directed graph
cycle detection in graph
graph data structure
detect cycle in graph
detect cycle in undirected graph
directed graph
graph dsa
cycle detection
finding cycle in a graph
anuj bhaiya java
cycle in graph
find cycle in graph
graph
detect cycle in a undirected graph
dfs graph
flattening a linked list
kangal vs pitbull+18
cycle detection dfs
cycle in a directed graph
cycle in a graph
detect a cycle in directed graph
directed acyclic graph
dsa
graph cycle detection
graph in dsa
graphs dsa
java anuj bhaiya
subarray with given sum
anuj bhai
anuj kumar sharma
bfs and dfs algorithm
connected graph
cycle detection in undirected graph
cycle in undirected graph
data structure and algorithm
data structures and algorithms
detect cycle in an undirected graph
dfs
dfs algorithm
dfs directed graph
dfs in graph
dfs in java
direct acyclic graph
dsa course
dsa one course
educative
graph data structure in java
graph dfs
graph problems
graph tutorial
graphs in java
java by anuj bhaiya
java graph
jeet hogi meri jeet yo yo honey singh
sliding window maximum
striver
tarjan algorithm
topological sort
topological sorting in graph
zig zag traversal

[@prathmeshadsod629]

One of the best teacher I have ever seen

[@rahulsahay19]

Good. My graph understanding with your videos are getting much clearer and robust. Thanks.

[@Mani_OnFire]

Superb explanation sir❤🎉

[@_sf_editz1870]

Simple clear and crisp

[@Miss__Nikita_K]

only explanation I could grasp!

[@designwithrehana]

You are doing amazing. Keep doing👌👌

[@AnujBhaiya]

Thank you 😊

[@vivekchaudhary3794]

Very clear explanation 🎉❤❤❤

[@aparnakanchi]

What an explanation bhaiyaa!!!😇😇Truly Amazing

[@_SOHAMSAMANTA]

@Anuj Bhaiya how many more videos left on Graph ? Please reply!

[@anjaliyadav9360]

Awesome Explanation!

[@suar_pilla]

Using DFS Iterative... Simple: public boolean hasCycleDirectedGraph(T src) { Set vertices = adjList.keySet(); //This will contain all the vertices that are processed/visited previously Set processedVertices = new HashSet(); //Check all paths even the disconnected ones for (T vertex : vertices) { //If the vertex is visited/processed previously then ignore if (!processedVertices.contains(vertex)) { HashSet visited = new HashSet(); boolean foundCycle = hasCycleDFSDirectedGraph(vertex, visited); if (foundCycle == false) { processedVertices.addAll(visited); //if no cycle found so far continue, with other paths if available hasCycleDFSDirectedGraph(src, visited); } else return true; } } //No cycle found so far after checking all vertices return false; } private boolean hasCycleDFSDirectedGraph(T src, Set visited) { Stack stack = new Stack(); stack.add(src); visited.add(src); while (!stack.isEmpty()) { T pop = stack.pop(); List neighbors = adjList.getOrDefault(pop, Collections.emptyList()); for (T neighbor : neighbors) { if (!visited.contains(neighbor)) { visited.add(neighbor); stack.add(neighbor); } else // if any path is leading to a previously visited node, that means it has a cycle return true; } } return false; }

[@veerendrashukla]

Very nice explanation, Anuj!

[@saurabhmina8671]

showing TLE

[@chandnibhatia1211]

One more alternative solution : push the elements in stack ..if there is a cycle ...the stack wil contain same element stack.contains(i) will return true ..if thats the case ..there is a cycle or else continue till the array length exhausts and if stack doesnt contain any i element ...that means no cycle

[@tanaykamath1415]

contains will take O(n) which is unnecessary

[@jayaswalrajp]

very nice explanation.. thank you so much

[@user-ej2df1ub3s]

thanks alot buhat bariya

[@mindbehaviour9195]

Thnx bhaiya ji 🙏

[@satyajeet7633]

Thank u Anuj bhaiya.

[@Ajay-wv1jh]

Thanks a lott❤❤

[@souhardyahalder3903]

Worked for java But showing TLE in cpp

[@zainabmalik7858]

excellent explanation!

[@malayasabar4108]

Boom 💥 💥

[@gautamsajwan111]

Bhiya y course complete kb hone wla h 😅

[@karansinghnegi9384]

*2050*

[@meetsoni1938]

Moj karadi bhaiya 😃😃💗

[@yashyadav7927]

bhaiya plz make 1 more video for directed graph bfs and dfs.. plz bhaiya

[@tech_wizard9315]

Please make a 60day roadmap for DSA beginner to crack tech giant's like Microsoft Amazon level companies in 60days

[@dillirajtimalsina]

haah benchod meah 1 saal se padraha huu DSA full time ab tuje 60d roadmap chaiye ,chal bsdk gand merwale

[@harshubhaigaming7882]

Which is best anuj sir OR apna college 🤔🤔🤔🤔🤔🤔

[@akshayroy3869]

Sir mera ek question h ki Mera 10th me 46% hai aur 12th me 56% to kya mujhe placement mil jaegi mca se

[@niloynath8458]

❤️❤️❤️

[@sanyamkothari4469]

Hello bhaiya, amazon november me hire karti hai interns , uska prepration kaise karu 3 mhine me??