Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

Leetcode Course Schedule problem solution

YASH PAL, 31 July 2024

In this Leetcode Course Schedule problem solution, There are a total of numCourses courses you have to take, labeled from 0 to numCourses – 1. You are given an array of prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Leetcode Course Schedule problem solution

Problem solution in Python.

def canFinish(self, numCourses, prerequisites):
        def cycle(v, G, R, B):
            if v in R: return True
            R.add(v)
            if v in G:
                for _v in G[v]:
                    if _v not in B and cycle(_v, G, R, B): return True
            R.remove(v); B.add(v)
            return False
        
        G, R, B = collections.defaultdict(list), set(), set()
        for p in prerequisites:
            G[p[0]].append(p[1])
        for v in G:
            if v not in B and cycle(v, G, R, B): return False
        return True

Problem solution in Java.

public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) return true;
        int n = numCourses;
        int[] vis = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; ++i) map.put(i, new ArrayList<Integer>());
        for (int[] p : prerequisites) {
            map.get(p[1]).add(p[0]);
        }
        for (int i = 0; i < n; ++i) {
            if (!dfs(i, vis, map)) return false;
        }
        return true;
    }

    private boolean dfs(int i, int[] vis, Map<Integer, List<Integer>> map) {
        if (vis[i] == 1) return false;
        if (vis[i] == 2) return true;
        vis[i] = 1;
        for (int next : map.get(i)) {
            if (!dfs(next, vis, map)) return false;
        }
        vis[i] = 2;
        return true;
    }

Problem solution in C++.

#define x a[i]
    #define first x[0]
    #define second x[1]
    #define pb push_back
    #define f q.front()
    bool canFinish(int n, vector<vector<int>>& a) {
        vector<int> adj[n+10];int i,j;
        queue<int> q;
        for(i=0;i<a.size();i++) 
        {
            adj[first].pb(second);
            q.push(second);
            while(!q.empty())
            {
                if(f==first) return 0;
                for(j=0;j<adj[f].size();j++)
                    q.push(adj[f][j]);
                q.pop();
            }
        }
        return 1;
    }

Problem solution in C.

struct adjnode{
    int dep;
    struct adjnode *next;
};
struct adjlist{
    struct adjnode *head;
};
struct graph{
    int v;
    struct adjlist *arr;
};
struct graph* create(int num){
    struct graph *g = (struct graph *)malloc(sizeof(struct graph));
    g->v = num;
    g->arr= (struct adjlist *)malloc(sizeof(struct adjlist)*num);
    for(int i=0;i<num;i++){
        g->arr[i].head = NULL;
    }
    return g;
}
void add_edge(struct graph *g, int src, int dest){
    struct adjnode *new = (struct adjnode *)malloc(sizeof(struct adjnode));
    new->dep = dest;
    new->next = g->arr[src].head;
    g->arr[src].head = new;
}

bool iscyclic(struct graph *g, bool *visited, bool *restack, int v){
    if (visited[v] == false){
        visited[v] = true;
        restack[v] = true;
        struct adjnode *cur = g->arr[v].head;
        while (cur){
            if (!visited[cur->dep] && iscyclic(g,visited,restack,cur->dep))
                return true;
            else if (restack[cur->dep]==true)
                return true;
            cur = cur->next;
        }
    }
    restack[v] = false;
    return false;
}
bool canFinish(int numCourses, int** prerequisites, int prerequisitesRowSize, int prerequisitesColSize) {
    struct graph *g = create(numCourses);
    int i;
    for (i=0;i<prerequisitesRowSize;i++){
        add_edge(g, prerequisites[i][0], prerequisites[i][1]);
    }
    bool visited[numCourses];
    bool restack[numCourses];
    for(i=0;i<numCourses;i++){
        visited[i] = false;
        restack[i] = false;
    }
    for(i=0;i<numCourses;i++){
        if(iscyclic(g,&visited[0], &restack[0],i))
            return false;
    }
    return true;
}

coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes