Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public boolean isCyclic(int V, int[][] edges) {
- ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
- for(int i=0; i<V; i++)
- {
- adj.add(new ArrayList<Integer>());
- }
- for(int [] edge : edges)
- {
- int u = edge[0];
- int v = edge[1];
- adj.get(u).add(v);
- }
- // to keep a track of nodes if they are visited or not
- boolean[] visited = new boolean[V];
- // to keep a track of nodes if they are visited in same path or not
- boolean[] pathVisited = new boolean[V];
- for(int i=0; i<V; i++)
- {
- if(visited[i] == false)
- {
- if(dfs(adj, visited, pathVisited, i))
- return true;
- }
- }
- return false;
- }
- public boolean dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, boolean[] pathVisited, int node)
- {
- visited[node] = true;
- pathVisited[node] = true;
- // traverse through neighbours
- for(int v : adj.get(node))
- {
- if(visited[v] == false)
- {
- if(dfs(adj, visited, pathVisited, v))
- return true;
- }
- // if neighbour node is visited already in same path earlier, then it creates a cycle now
- else if(pathVisited[v] == true)
- return true;
- }
- // unmark the current node from pathVisited array because we are going to check another path now
- pathVisited[node] = false;
- return false;
- }
- }
RAW Paste Data
Copied
