Leetcode Course Schedule problem solution

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