DFS find cycle

find-cycle-recursive.cpp

#include<vector>
#include<unordered_map>
#include<stack>
#include<iostream>

using namespace std;

bool findCycle(int head, unordered_map<int, vector<int>> &graph, vector<bool> &black, vector<bool> &gray){
    if (black[head]){
        return false;
    }

    if (gray[head]){
        return true;
    }

    gray[head] = true;
    const auto children = graph[head];
    bool ret = false;
    for (int child : children){
        ret = findCycle(child, graph, black, gray);
        if (ret){
            break;
        }
    }
    gray[head] = false;
    black[head] = true;

    return ret;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites){
    //build adjacency list o(n)
    unordered_map<int, vector<int>> graph;
    for(auto prereq : prerequisites){
        int course = prereq[1];

        int required = prereq[0];

        if (graph.find(course) == graph.end()) { //add it
            vector<int> foo;
            graph[course] = foo;
        }
        graph[course].push_back(required);
    }


    //dfs each node in our graph checking for cycles
    vector<bool> black(numCourses);
    vector<bool> gray(numCourses);
    for (auto node : graph){
        if (findCycle(node.first, graph, black, gray)){
            return false;
        }
    }
    return true;
}