> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/13.course-schedule-ii.md).

# 16.Course Schedule II

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 1:
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].

Example 2:
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].

Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
```

## Solution: (Topological Sort)

**Using Stack and DFS**

```cpp
class Solution
{
public:
    bool isCycle(vector<int> v[], vector<int> &col, int src)
    {

        col[src] = 1;

        for (int i = 0; i < v[src].size(); i++)
        {
            int node = v[src][i];

            if (col[node] == 1)
            {
                return true;
            }

            if (col[node] == 0)
            {
                if (isCycle(v, col, node))
                {
                    return true;
                }
            }
        }
        col[src] = 2;
        return false;
    }

    void topologicalSort(vector<int> v[], vector<bool> &vs, stack<int> &s, int src)
    {

        vs[src] = 1;

        for (int i = 0; i < v[src].size(); i++)
        {
            int node = v[src][i];

            if (!vs[node])
            {
                topologicalSort(v, vs, s, node);
            }
        }

        s.push(src);
        return;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
    {

        vector<int> v[numCourses];

        for (int i = 0; i < prerequisites.size(); i++)
        {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];

            v[b].push_back(a);
        }

        vector<int> ans;
        vector<int> col(numCourses, 0);
        for (int i = 0; i < numCourses; i++)
        {
            if (col[i] == 0)
            {
                if (isCycle(v, col, i))
                {
                    return ans;
                }
            }
        }

        stack<int> s;

        vector<bool> vs(numCourses, false);

        for (int i = 0; i < numCourses; i++)
        {
            if (!vs[i])
            {
                topologicalSort(v, vs, s, i);
            }
        }

        while (!s.empty())
        {
            ans.push_back(s.top());
            s.pop();
        }

        return ans;
    }
};
```

## Solution: (Topological Sort)

**Using Queue and Indegree**

```cpp
class Solution
{
public:
    vector<int> bfs(vector<int> v[], vector<int> &indeg)
    {
        queue<int> q;
        
        for (int i = 0; i < indeg.size(); i++)
        {
            if (indeg[i] == 0)
            {
                q.push(i);
            }
        }
        
        vector<int> res;
        while (!q.empty())
        {
            int x = q.front();
            res.push_back(x);
            q.pop();

            for (int i = 0; i < v[x].size(); i++)
            {
                indeg[v[x][i]] = indeg[v[x][i]] - 1;
                if (indeg[v[x][i]] == 0)
                {
                    q.push(v[x][i]);
                }
            }
        }
        return res;
    }
    
    vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
    {

        vector<int> indeg(numCourses);
        vector<int> v[numCourses];

        for (int i = 0; i < prerequisites.size(); i++)
        {
            v[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }

        for (int i = 0; i < numCourses; i++)
        {
            for (int j = 0; j < v[i].size(); j++)
            {
                indeg[v[i][j]]++;
            }
        }

        vector<int> res;
        res = bfs(v, indeg);
        if (res.size() == numCourses)
        {
            return res;
        }

        vector<int> k;
        return k;
    }
};
```

**Time Complexity: O(V + E)**