cycleCheckDGDfs.java

import java.util.*;
import java.io.*;
import java.lang.*;

class DriverClass {
    public static void Main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();

        while(t-->0){

            ArrayList<ArrayList<Integer>>list=new ArrayList<>();
            int V=sc.nextInt();
            int E=sc.nextInt();

            for(int i=0;i<V+1;i++){
                list.add(i, new ArrayListInteger>());

            for(int i=0;i<E;i++){
                int u=sc.nextInt();
                int v=sc.nextInt();
                list.get(u).add(v);
            }
            
            if(new Solution().isCyclic(V, list) == true)
              System.out.println("1");
            else
                System.out.println("0");
            }
    }
}

class Solution{
    private boolean checkCycle(int node, ArrayList<ArrayList<Integer>> adj, int[] visited, int[] dfsVis){
        vis[node]=1;
        dfsVis[node]=1;

        for(Integer it:adj.get(node)){
            if(vis[it]==0){
                if(checkCycle(it, adj, visited, dfsVis)==true) {
                    return true;
                }
            }
            else if(dfsVis[it]==1){
                return true;
            }
        }
        dfsVis[node]=0;
        return false;
    }
    public boolean isCyclic(int N, ArrayList<ArrayList<Integer>> adj){
        int vis[]=new int[N];
        int dfsVis[]=new int[N];
        for(int i=0; i<N; i++){
            if(visited[i]==0){
                if(checkCycle(i, adj, visited, dfsVis)==true) {
                    return true;
                }
            }
        }
        return false;
    }
}