C++ straightforward DFS solution

  • 2
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (numCourses == 0) return true;
        vector<vector<int>> graph(numCourses);
        for (auto p: prerequisites) {
        vector<bool> visited(numCourses, false);
        unordered_set<int> startNodes;
        for (int i = 0; i < numCourses; i++) startNodes.insert(i);
        while (!startNodes.empty()) {
            int node = *(startNodes.begin());
            if (dfsLoopDetection(graph, visited, node, startNodes)) return false;
        return true;
    bool dfsLoopDetection(const vector<vector<int>>& graph, vector<bool>& visited, int node, unordered_set<int>& startNodes) {
        visited[node] = true;
        for (int neighbor: graph[node]) {
            if (visited[neighbor]) return true;
            if (dfsLoopDetection(graph, visited, neighbor, startNodes)) return true;
        visited[node] = false;
        return false;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.