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.

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;
}