Course Schedule II

There are a total of n courses you have to take labeled from 0 to n - 1.
Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = {{1,0}}
Output: order={0,1}

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CourseScheduleII {
    // store the indegree of all the nodes
    static HashMap<Integer, Integer> indegre;
    static List<Integer> ans;

    public static void main(String[] args) {
        int numCourses = 2;
        int prerequisites[][] = { { 1, 0 } };
        int order[] = findOrder(numCourses, prerequisites);
        System.out.println(Arrays.toString(order));
    }

//topoplogical sort function
    public static boolean kahn(int n, ArrayList<ArrayList<Integer>> adj) {
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < n; i++)
            if (indegre.get(i) == 0)
                q.add(i);

        while (!q.isEmpty()) {
            int curr = q.poll();
            ans.add(curr);
            for (int child : adj.get(curr)) {
                indegre.put(child, indegre.getOrDefault(child, 0) - 1);
                if (indegre.get(child) == 0)
                    q.add(child);
            }
        }
        if (ans.size() == n)
            return true;
        return false;
    }

    // function to find the order in
    // which courses will done
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        ans = new ArrayList<>();
        indegre = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
            indegre.put(i, 0);
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            adj.get(b).add(a);
            indegre.put(a, indegre.getOrDefault(a, 0) + 1);
        }
        if (kahn(numCourses, adj)) {
            return ans.stream().mapToInt(Integer::intValue).toArray();
        }
            return new int[] {};
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> arr[100001];
int in[1000001];
vector<int> ans;

//function for topological sort
bool kahn(int n)
{
        queue<int> q;
        for(int i=0;i<n;i++)
          if(in[i]==0)
                q.push(i);
      while(!q.empty())
      {
          int curr=q.front();
          ans.push_back(curr);
          q.pop();
          for(int child:arr[curr])
          {
              in[child]--;
              if(in[child]==0)
                    q.push(child);
          }
      }
      if(ans.size()==n)
            return true;
        return false;
}

//function to find the order in 
//which courses will done
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
{
              
        for(int i=0;i<numCourses;i++)
        {
            arr[i].clear();
            in[i]=0;
        }
        ans.clear();
        for(int i=0;i<prerequisites.size();i++)
         {
           int a=prerequisites[i][0];
           int b=prerequisites[i][1];
            arr[b].push_back(a);
            in[a]++;
         }
        if(kahn(numCourses))
            return ans;
        else
             return {};
} 
int main()
{
    int numCourses = 2;
    vector<vector<int>> prerequisites ={{1,0}};
    vector<int> order=findOrder(numCourses,prerequisites);
    for(int i=0;i<order.size();i++)
       cout<<order[i]<<" ";
    return 0;
}