207. Course Schedule

Description of Problem

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] = [ai, bi] indicates that you must take course b_i first if you want to take course a_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_i, b_i < numCourses
• All the pairs prerequisites[i] are unique.

Solution

Tags: Graph Theory

Explanation

The method is the same as 210. Course Schedule II. By topological sorting, we can detect the cycle in the graph.

Code (Rust)

use std::collections::HashMap;

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let num_courses = num_courses as usize;

        let mut adj_list : Vec<Vec<usize>> = vec![ vec![] ; num_courses ];
        let mut is_gray : Vec<bool> = vec![false; num_courses];
        let mut is_black : Vec<bool> = vec![false; num_courses];

        for p in prerequisites.into_iter(){
            let (c1, c2) = (p[1] as usize, p[0] as usize);
            adj_list[c1].push(c2);
        }

        let mut has_loop = false;

        for vertex in (0..num_courses) {
            if !is_black[vertex] && !is_gray[vertex] && !has_loop {
                has_loop = Self::visit(vertex, &adj_list, &mut is_gray, &mut is_black);
            }
        }

        !has_loop
    }

    fn visit(
        vertex : usize, 
        adj_list : &Vec<Vec<usize>>,
        is_gray : &mut Vec<bool>,
        is_black : &mut Vec<bool>
    ) -> bool {
            for &v in adj_list[vertex].iter() {
                match (is_black[v], is_gray[v]){
                    (false, false) => {
                        is_gray[v] = true;
                        if Self::visit(v, adj_list, is_gray, is_black) == true {
                            return true;
                        }
                        is_gray[v] = false;
                    }
                    (false, true) => return true,
                    _ => {}
                }
            }
        is_black[vertex] = true;
        return false;
    }
}