Time Cost

16min06s

Implementation

Using 3-Color DFS to solve this problem. Note that we have to transform the input prerequisites to directed graph to use this algorithm.

Code

• Solution

  class Solution {
  public:
    bool dfs(int u, const vector<vector<int>>& graph, vector<int>& state) {
        state[u] = 1; // visiting
        for (int v : graph[u]) {
            if (state[v] == 1) return true;             // back-edge => cycle
            if (state[v] == 0 && dfs(v, graph, state)) return true;
        }
        state[u] = 2; // done
        return false;
    }
  
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& p : prerequisites) {
            int a = p[0], b = p[1];
            graph[b].push_back(a); // b -> a
        }
  
        vector<int> state(numCourses, 0);
        for (int i = 0; i < numCourses; ++i) {
            if (state[i] == 0 && dfs(i, graph, state)) return false;
        }
        return true;
    }
  };