Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

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

Approach

Java

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

public class CourseSchedule {
    // store the indegree of all the nodes
    static HashMap<Integer, Integer> indegre = new HashMap<>();

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

//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);
        int cnt = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            cnt++;
            for (int child : adj.get(curr)) {
                indegre.put(child, indegre.getOrDefault(child, 0) - 1);
                if (indegre.get(child) == 0)
                    q.add(child);
            }
        }
        if (cnt == n)
            return true;
        return false;
    }

//function to check for course schedule
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        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(a).add(b);
            indegre.put(b, indegre.getOrDefault(b, 0) + 1);
        }
        if (kahn(numCourses, adj))
            return true;
        return false;
    }

}

C++

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

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

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

//function to check for course schedule
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
{
        for(int i=0;i<numCourses;i++)
        {
            arr[i].clear();
            in[i]=0;
        }
        for(int i=0;i<prerequisites.size();i++)
         {
            int a=prerequisites[i][0];
            int b=prerequisites[i][1];
            arr[a].push_back(b);
            in[b]++;
         }
        if(kahn(numCourses))
              return true;
        return false;
}
int main()
{
   int  numCourses = 2;
   vector<vector<int>> prerequisites ={{1,0},{0,1}};
   if(canFinish(numCourses,prerequisites))
     cout<<"true";
   else
     cout<<"false";
   return 0;
}