class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { /* Q18 of graph playlist , we will do this through kahn's algo or topological sort assume the problem to be a graph where ever node has a dependency/prequisite to another node also known as indegree. */ //taking input int n = numCourses; ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); //initializing arraylist for(int i = 0 ; i < n ; i++) graph.add(new ArrayList<>()); //making graph for(int pre[] : prerequisites) graph.get(pre[1]).add(pre[0]); //calling kahn's algo ArrayList<Integer> ans = kahn(n , graph); //if all vertix are covered in kahn's algo return true , else false if(ans.size() == n ) return true; return false; } public ArrayList<Integer> kahn(int n , ArrayList<ArrayList<Integer>> graph){ ArrayList<Integer> ans = new ArrayList<>(); //can also count instead arraylist //finding indegree int[] indegree = new int[n]; for(int i = 0 ;i < n ; i++){ for(int nbr : graph.get(i)) indegree[nbr] ++; } //making a q and adding all nodes with indegree 0 LinkedList<Integer> q = new LinkedList<>(); for(int i = 0 ; i < n ;i++){ if(indegree[i] == 0) q.addLast(i); } //now running kahn's algo while(q.size()>0){ int rem = q.removeFirst(); ans.add(rem); //storing in topological order //decreasing indegree/dependency of neighours for(int nbr : graph.get(rem)){ indegree[nbr] --; //if node's indegree becomes 0 we add it to the q if(indegree[nbr] == 0) q.addLast(nbr); } } return ans; } }