topoSort.java

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

class Main{
    public static void main(String[] args){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(reader.readLine());

        while(t--){
            ArrayList<ArrayList<Integer>>list=new ArrayList<>();
            String st[]=read.readLine().trim().split("\\s+");
            int edg=Integer.parseInt(st[0]);
            int nov=Integer.parseInt(st[1]);

            for(int i=0; i<nov+1; i++)
              list.add(new ArrayList<Integer>());

            int p=0;
            for(int i=1;i<=edg;i++){
                String s[]=read.readLine().trim().split("\s+");
                int u=Integer.parseInt(s[0]);
                int v=Integer.parseInt(s[1]);
                list.get(u).add(v);
            }

            int[] res= new Solution().topoSort(nov, list);

            if(check(list, nov, res)==true)
               System.outrintln("1");
            else
                System.out.println("0");

        }
    }

    static boolean check(ArrayList<ArrayList<Integer>>list, int V, int[] res){
        int[] map=new int[V];
        for(int i=0;i<V;i++){
            map[res[i]]=1;
        }
        for(int i=0;i<V;i++){
            for(int v:list.get(i)){
                if(map[i]>map[v])
                    return false;
            }
        }
        return true;
    }
}

class Solution{
    static void findTopoSort(int node, int vis[], ArrayList<ArrayList<Integer>> adj, Stack<Integer>st) {
        vis[node] =1;
        for(Integer it:adj.get(node)){
            if(vis[it]==0){
                findTopoSort(it, vis, adj, st);
            }
        }
          st.push(node);
    }

    static int[] topoSort(int N, ArrayList<ArrayList<Integer>> adj){
        Stack<Integer> st=new Stack<Integer>();
        int vis[]=new int[N];

        for(int i=0; i<N; i++){
            if(vis[i]==0){
                findTopoSort(i, vis, adj, st);
            }
        }

        int topo[]=new int[N];
        int ind=0;
        while(!st.isEmpty()){
            topo[ind++]=st.pop();
        }
        return topo;
    }
}