Course_Schedule_II.java

//Leetcode 210. Course Schedule II
//Question - https://leetcode.com/problems/course-schedule-ii/
//Kahn's Topological Sort

classSolution {
publicint[] findOrder(intnumCourses, int[][] prerequisites) {
intresult[] = newint[numCourses];
intcntVertex = 0;
Queue<Integer> inDegree0 = newLinkedList<>();
intinDegree[] = newint[numCourses];
Arrays.fill(inDegree,0);

for(inti=0 ; i<prerequisites.length ; i++){
inDegree[prerequisites[i][0]]++;
 }

for(inti=0 ; i<numCourses ; i++){
if(inDegree[i]==0) inDegree0.add(i);
 }

while(!inDegree0.isEmpty()){
intcurr = inDegree0.poll();
ArrayList<Integer> neighbours = findNeighbours(prerequisites,curr);
result[cntVertex] = curr;

for(intneighbour : neighbours){
if(--inDegree[neighbour]==0) inDegree0.add(neighbour);
 }
cntVertex++;
 }

if(cntVertex!=numCourses) return (newint[0]);
elsereturnresult;
 }

publicArrayList<Integer> findNeighbours(int[][] prerequisites, intv){
ArrayList<Integer> neighbours = newArrayList<Integer>();
for(inti=0;i<prerequisites.length;i++){
if(prerequisites[i][1]==v) neighbours.add(prerequisites[i][0]);
 }
returnneighbours;
 }
}