Course Schedule | Deadlock Detection | Graph Coloring

This video explains a very important programming interview problem which is, given a course schedule with prerequisites for each course, find if it is possible to take all the courses satisfying the prerequisites for each course. If it is possible then return TRUE otherwise FALSE.This problem is same as detecting a deadlock in a single resource instance distributed system.In such a system, if we have a cycle then we a deadlock.Therefore, this problem further reduces to finding cycle in a graph.I have shown the solution using graph coloring to detect cycle in a directed graph.

class Solution {
    bool isCyclic(vector<vector<int>>& adj,vector<int>& visited,int curr)
    {
        if(visited[curr]==2)
            return true;
        
        visited[curr] = 2;
        for(int i=0;i<adj[curr].size();++i)
            if(visited[adj[curr][i]]!=1)
                if(isCyclic(adj,visited,adj[curr][i]))
                    return true;
        
        visited[curr] = 1;
        return false;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        vector<vector<int>> adj(numCourses);
        //Make adjacency matrix (Directed graph)
        for(int i=0;i<prerequisites.size();++i)
            adj[prerequisites[i][0]].push_back(prerequisites[i][1]);
        
        vector<int> visited(numCourses,0);
        for(int i=0;i<numCourses;++i)
            if(visited[i]==0)
                if(isCyclic(adj,visited,i))
                    return false;
        
        return true;
    }
};

Write a comment