[LeetCode] Course Schedule

The question can be found here: https://leetcode.com/problems/course-schedule/

Analysis:

You can just think of the problem checking if circle exists in a tree. Just need to note:
1) In a search path from any node,  if any node in the path appears more than once, there is a circle.
2) If a node is in a search path that doesn't have circle, any other searches should stop once they meet the node.
These will make the complexity O(n).
DFS solution:

See Course Schedule II

class Solution {
public:
    bool hasCircle(unordered_map<int, vector<int>> &map, 
                int cur, unordered_set<int>& visited)
    {
        if(!map.count(cur) || map[cur].size()==0) return false;
        //if cur course was visited, there is a circle
        if(visited.count(cur)) return true;
        visited.insert(cur);
        for(int i=0;i < map[cur].size();i++)
        {
            if(hasCircle(map, map[cur][i],visited)) return true;
        }  
        //the course cur is good, any other searches should not check it again.
        map[cur].clear();
        return false;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        unordered_map<int, vector<int> > map;
        unordered_set<int> visited;
        for(auto p:prerequisites) map[p[0]].push_back(p[1]);
        for(auto it:map)
        {
            if(hasCircle(map, it.first, visited)) return false;
            visited.clear();
        }
        return true;
    }
};