1. import java.util.*;
  2. public class Solution {
  3.   /** 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. */
  4.   public static boolean detectCycleInDirectedGraph(int n, ArrayList < ArrayList < Integer >> edges) {
  5.  
  6.     // Step 1: Create adjacency list
  7.     ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
  8.     for(int i=0; i<=n; i++)
  9.     {
  10.       adj.add(new ArrayList<>());
  11.     }
  12.  
  13.     // Step 2: Fill adjacency list and indegree array
  14.     int[] indegree = new int[n+1];
  15.     for(ArrayList<Integer> edge : edges) {
  16.       int u = edge.get(0);
  17.       int v = edge.get(1);
  18.  
  19.       adj.get(u).add(v);
  20.       indegree[v]++;
  21.     }
  22.  
  23.     //Step-3 check which all nodes has an indegree as 0, add those nodes to queue
  24.     Queue<Integer> q = new LinkedList<>();
  25.     for(int i=1; i<=n; i++)
  26.     {
  27.       if(indegree[i] == 0)
  28.         q.add(i);
  29.     }
  30.  
  31.     // Step-4: Process queue
  32.     int count = 0;
  33.     while(!q.isEmpty())
  34.     {
  35.       int node = q.poll();
  36.       count++;
  37.  
  38.       // traverse all neighbour of current node
  39.       for(int u : adj.get(node))
  40.       {
  41.         indegree[u]--;
  42.         if(indegree[u] == 0)
  43.           q.add(u);
  44.       }
  45.     }
  46.  
  47.     // Step-5: Check cycle
  48.     return count != n;
  49.   }
  50. }