You are given numCourses labeled from 0 to numCourses - 1 and a list of prerequisite pairs prerequisites where prerequisites[i] = [a, b] means that course a depends on course b (i.e., b must be taken before a). Determine if its possible to finish all courses, that is, whether the dependency graph contains no cycles.

Example

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Course 1 requires course 0. This forms a valid sequence.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Both courses depend on each other, creating an impossible cycle.

Approach

Model courses as vertices and a prerequisite [a, b] as a directed edge from b to a. The problem reduces to cycle detection in a directed graph. Two common strategies exist:

• Kahn's algorithm (BFS) using in-degree and a queue.
• DFS with three-state coloring to detect back edges.

1. BFS – Kahn’s Algorithm

Maintain the in-degree of each vertex. Enqueue all vertices with zero in-degree. Process the queue: for each removed vertex, decrement the in-degree of its neighbors and enqueue any that become zero. If the number of processed vertiecs equals numCourses, the graph is acyclic.

#include <vector>
#include <queue>

using namespace std;

class SolutionBFS {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        
        for (auto& edge : prerequisites) {
            int dependent = edge[0];
            int prerequisite = edge[1];
            graph[prerequisite].push_back(dependent);
            ++indegree[dependent];
        }
        
        queue<int> zero_queue;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) zero_queue.push(i);
        }
        
        int courses_taken = 0;
        while (!zero_queue.empty()) {
            int course = zero_queue.front(); zero_queue.pop();
            ++courses_taken;
            for (int next_course : graph[course]) {
                --indegree[next_course];
                if (indegree[next_course] == 0) {
                    zero_queue.push(next_course);
                }
            }
        }
        
        return courses_taken == numCourses;
    }
};

2. DFS – Cycle Detection via Three-State Coloring

Assign each vertex one of three states:

• 0 – not visited
• 1 – currently in the recursion stack (visiting)
• 2 – fully processed

A back edge to a vertex with state 1 indicates a cycle. The dfs function returns true if a cycle is found.

#include <vector>

using namespace std;

class SolutionDFS {
    vector<vector<int>> graph;
    vector<int> state; // 0: unvisited, 1: visiting, 2: done
    
    bool dfs(int course) {
        state[course] = 1;
        for (int neighbor : graph[course]) {
            if (state[neighbor] == 0) {
                if (dfs(neighbor)) return true;
            } else if (state[neighbor] == 1) {
                return true; // cycle detected
            }
        }
        state[course] = 2;
        return false;
    }
    
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        graph.resize(numCourses);
        state.assign(numCourses, 0);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        
        for (int i = 0; i < numCourses; ++i) {
            if (state[i] == 0) {
                if (dfs(i)) return false;
            }
        }
        return true;
    }
};

3. Complete Example with Input Parsing

Reading numCourses and a string formatted as [[1,0],[0,1]], parsing the 2D vector, and invoking the BFS solution.

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<vector<int>> parse_2d_vector(const string& s) {
    vector<vector<int>> result;
    string temp = s;
    // Remove outer brackets
    if (!temp.empty() && temp.front() == '[') temp.erase(0, 1);
    if (!temp.empty() && temp.back() == ']') temp.pop_back();
    
    size_t pos = 0;
    while (pos < temp.size()) {
        if (temp[pos] == '[') {
            size_t end = temp.find(']', pos);
            string inner = temp.substr(pos + 1, end - pos - 1);
            vector<int> pair;
            stringstream ss(inner);
            string item;
            while (getline(ss, item, ',')) {
                pair.push_back(stoi(item));
            }
            result.push_back(pair);
            pos = end + 1;
        } else {
            ++pos;
        }
    }
    return result;
}

int main() {
    int numCourses;
    cin >> numCourses;
    string prereq_str;
    cin >> prereq_str;
    
    vector<vector<int>> prerequisites = parse_2d_vector(prereq_str);
    
    SolutionBFS solver;
    cout << boolalpha << solver.canFinish(numCourses, prerequisites) << endl;
    return 0;
}