Course Schedule -- LeetCode

[Question]
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

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.

[Analysis]
This is equivalent to the question of finding a circle in a Directed Graph (DiGraph). Using DFS and find if one path will cross itself.

Another approach is to use BFS. Define a node without incoming going edges as Root Node. The assumption is a DiGraph without Root Node must have a circle -- this can be proven by mathematical induction. Therefore, remove Root Node one by one from the DiGraph one by one; if the reminding graph does not have Root Node, it has a circle. Time complexity O(E+V).

[Solutions]
//-- DFS --
class Solution {
public:
    vector<unordered_set<int> > graph;
    vector<bool> visited;
   
    bool dfs_findCircle(int i, unordered_set<int> &path) {
        if (visited[i]) {
            return (path.find(i)!=path.end());
        }
        visited[i] = true;
        path.insert(i);
        for(auto j : graph[i]) {
            if (dfs_findCircle(j, path)) return true;
        }
        path.erase(i);
        return false;
    }
   
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (prerequisites.empty()) return true;
        visited.resize(numCourses, false);
        graph.resize(numCourses, unordered_set<int>() );
        for (auto p: prerequisites) {
            graph[p.first].insert(p.second);
        }
        for (int i=0; i<numCourses; i++) {
            if (!visited[i]) {
                unordered_set<int> set;
                bool found = dfs_findCircle(i, set);
                if (found) return false;
            }
        }
        return true;
    }
}; 
 
//-- BFS --
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (prerequisites.empty()) return true;
       
        unordered_set <int> src;
        unordered_map <int, unordered_set<int>> fwd, bwd;
       
        for (auto pair: prerequisites) {
            src.insert(pair.first);
            fwd[pair.first].insert(pair.second);
            bwd[pair.second].insert(pair.first);
        }
       
        for (auto& x: bwd) src.erase(x.first);

        while (!src.empty()) {
            unordered_set<int> src1;
            for(auto x: src) {
                for(auto y: fwd[x]) {
                    bwd[y].erase(x);
                    if (bwd[y].empty()) {
                        src1.insert(y);
                    }
                }
                fwd.erase(x);
            }
            src = src1;
        }
           
        return fwd.empty();
    }
};