Detect cycle in directed graph
Java
Hard
6 views
Problem Description
Task: given n and edges, detect if there is a cycle (directed). Use DFS + recursion stack.
Output Format
Return value
Constraints
n can be up to 1e5; avoid heavy recursion if needed.
Official Solution
static boolean hasCycle(int n,int[][] edges){java.util.ArrayList<java.util.ArrayList<Integer>> g=new java.util.ArrayList<>();for(int i=0;i<n;i++) g.add(new java.util.ArrayList<>());for(int[] e:edges) g.get(e[0]).add(e[1]);int[] st=new int[n];for(int i=0;i<n;i++) if(st[i]==0 && dfs(i,g,st)) return true;return false;}static boolean dfs(int u,java.util.ArrayList<java.util.ArrayList<Integer>> g,int[] st){st[u]=1;for(int v:g.get(u)){if(st[v]==1) return true; if(st[v]==0 && dfs(v,g,st)) return true;}st[u]=2;return false;}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!