:orphan:

Course Schedule
===============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/course-schedule/

There are a total of ``numCourses`` courses you have to take, labeled
from ``0`` to ``numCourses - 1``. You are given an array
``prerequisites`` where
``prerequisites[i] = [a``\ :sub:```i```\ ``, b``\ :sub:```i```\ ``]``
indicates that you **must** take course ``b``\ :sub:```i``` first if you
want to take course ``a``\ :sub:```i```.

- 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``.

 

**Example 1:**

::


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

**Example 2:**

::


   Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
   Output: false
   Explanation: There are a total of 2 courses to take. 
   To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

**Constraints:**

- ``1 <= numCourses <= 2000``
- ``0 <= prerequisites.length <= 5000``
- ``prerequisites[i].length == 2``
- ``0 <= a``\ :sub:```i```\ ``, b``\ :sub:```i```\ ``< numCourses``
- All the pairs prerequisites[i] are **unique**.

.. highlight:: python

Pattern
-------
Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Approaches
----------

.. tab-set::

    .. tab-item:: Topological Sort

        **Code**

        .. literalinclude:: ../problems/medium/course-schedule/course_schedule__topological_sort.py
            :language: python
            :lines: 9-

        **Test**

        >>> from course_schedule__topological_sort import canFinish
        >>> canFinish(2, [[1, 0]])
        True
        >>> canFinish(2, [[1, 0], [0, 1]])
        False

        .. autofunction:: course_schedule__topological_sort.canFinish