[Google Question][LeetCode] Course Schedule II

Problem: There are a total of n courses you have to take labelled from 0 to n - 1. Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Input: numCourses = 1, prerequisites = []
Output: [0]

Approach:  Basically if you see it is clear example of Topological Sorting. We just need to take care of cycles in the Graph as if there is a cycle exits that means all the course can't be finished. Here are the two steps which we need to take:

1. Build a directed graph using prerequisites. If a prerequisite is [1, 0] that means there is an edge from a node with value 0 to node with value 1.
2. Topological sort.

That's all!

 

Implementation in C#:

    public int[] FindOrder(int numCourses, int[][] prerequisites) 

    {

        var graph = this.BuildGraph(numCourses, prerequisites);

        bool[] visited = new bool[numCourses];

        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < numCourses; ++i)

        {

            if (!visited[i])

            {

                bool[] onCycle = new bool[numCourses];

                bool isCycle = false;

                this.TopologicalSort(i, graph, visited, stack, onCycle, ref isCycle);

                

                if (isCycle)

                {

                    return new int[] {};

                }

            }

        }        

        int[] courseOrder = new int[numCourses];

        for (int i = 0; i < numCourses; ++i)

        {

            courseOrder[i] = stack.Pop();

        }        

        return courseOrder;

    }

    

    private void TopologicalSort(int course, Dictionary<int, List<int>> graph, bool[] visited, Stack<int> stack, bool[] onCycle, ref bool isCycle)

    {

        if (isCycle)

        {

            return;

        }

        visited[course] = true;

        onCycle[course] = true;        

        foreach (int child in graph[course])

        {

            if (onCycle[child])

            {

                isCycle = true;

                return;

            }            

            if (!visited[child])

            {

                this.TopologicalSort(child, graph, visited, stack, onCycle, ref isCycle);

            }

        }

        onCycle[course] = false;

        stack.Push(course);

    }

    

    private Dictionary<int, List<int>> BuildGraph(int numCourses, int[][] prerequisites)

    {

        var graph = this.InitializeGraph(numCourses);

        foreach (var prerequisite in prerequisites)

        {

            graph[prerequisite[1]].Add(prerequisite[0]);

        }

        return graph;

    }

    

    private Dictionary<int, List<int>> InitializeGraph(int numCourses)

    {

        var graph = new Dictionary<int, List<int>>();

        for (int i = 0; i < numCourses; ++i)

        {

            graph[i] = new List<int>();

        }

        return graph;

    }

Complexity: O(V + E) where is V is the number of nodes and E is the number of Edges.