Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Solution {
- /** In a Directed Acyclic Graph (DAG), topological sorting can process all nodes. If some nodes cannot be processed due to non-zero indegree, a cycle exists. */
- // Step 1: Create adjacency list
- ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
- for(int i=0; i<=n; i++)
- {
- adj.add(new ArrayList<>());
- }
- // Step 2: Fill adjacency list and indegree array
- int[] indegree = new int[n+1];
- for(ArrayList<Integer> edge : edges) {
- int u = edge.get(0);
- int v = edge.get(1);
- adj.get(u).add(v);
- indegree[v]++;
- }
- //Step-3 check which all nodes has an indegree as 0, add those nodes to queue
- Queue<Integer> q = new LinkedList<>();
- for(int i=1; i<=n; i++)
- {
- if(indegree[i] == 0)
- q.add(i);
- }
- // Step-4: Process queue
- int count = 0;
- while(!q.isEmpty())
- {
- int node = q.poll();
- count++;
- // traverse all neighbour of current node
- for(int u : adj.get(node))
- {
- indegree[u]--;
- if(indegree[u] == 0)
- q.add(u);
- }
- }
- // Step-5: Check cycle
- return count != n;
- }
- }
RAW Paste Data
Copied
