C# - iterative BFS - try to remove prereqs - clear explanation


  • 1

    this is a directional graph problem where courses are vertices and a prereqs are edges from prereq to it's course. Build the graph as a list of prereqs and their courses. Also keep a count of the number of prereqs for a course.

    Start with courses with zero prereqs and do BFS to try and bring all prereq counts to zero. With each round look at all courses linked to the prereq and reduce their count by 1. If that count is already at zero this is a cycle, and if their count now becomes zero add this course to the queue (it can now be taken and used as a prereq for other courses). Finally if all courses have removed all their prereqs they can all be taken.

        public bool CanFinish(int numCourses, int[,] prerequisites)
        {
            // map of courses which have this course as a prereq
            List<int>[] map = new List<int>[numCourses];
            for (int i = 0; i < numCourses; i++) map[i] = new List<int>();
    
            // counter of how many prereqs for a course
            int[] preCnt = new int[numCourses];
    
            // build map and counter
            for (int i = 0; i < prerequisites.GetLength(0); i++)
            {
                int course = prerequisites[i, 0];
                int pre = prerequisites[i, 1];
                map[pre].Add(course);
                preCnt[course]++;
            }
    
            // BFS - start will all courses with no prereqs
            // process each item
            //   - any dependent course that has no prereqs - this is a cycle
            //   - if removing this prereq brings it's count to zero - add this course for processing
            Queue<int> queue = new Queue<int>();
            for (int i = 0; i < numCourses; i++) if (preCnt[i] == 0) queue.Enqueue(i);
            
            while (queue.Count > 0)
            {
                int pre = queue.Dequeue();
                foreach (int c in map[pre])
                {
                    if (preCnt[c] == 0) return false;
                    preCnt[c]--;
                    if (preCnt[c] == 0) queue.Enqueue(c);
                }
            }
    
            // all prereqs removed?
            return preCnt.All(x => x == 0);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.