[LeetCode] Course Schedule II

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

Analysis:
1) find the sink node which doesn't have any directed neighbors
2) put it at the head of the list and remove it
3) repeat 1) and 2)
See more at :https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html

class Solution {
    bool isSinkNode(unordered_map<int, unordered_set<int>>& map, 
                    vector<int> &visited, int cur, 
                    vector<int> & res, bool &cycle){
                        
        if(visited[cur] == 1) 
        {
            cycle = true;
            return false;
        }
        // 1 means its being visited in a path
        visited[cur] = 1;
        int nonSinkNeighbors = map[cur].size();
        for(auto e: map[cur])
        {
            if(visited[e] == 2|| 
                isSinkNode(map, visited, e,
                res, cycle)) nonSinkNeighbors--;
            else if(cycle) return false;
        }
        // if all the neighbors are sink node
        if(0 == nonSinkNeighbors) 
        {
            res.push_back(cur);
            //2 means this node is a sink node
            visited[cur] = 2;
        }
        // 3 means its visited in a path but not a sink node
        // we need to set it a value other than 1 to 
        else visited[cur] = 3; 
        return visited[cur] == 2;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        unordered_map<int, unordered_set<int>> map;
        for(auto p: prerequisites) map[p.first].insert(p.second);
        bool cycle = false;
        
        vector<int> visited(numCourses, 0);
        for(int i=0;i<numCourses;i++)
        {
            //0 means its not ever visited.
            if(visited[i] == 0) isSinkNode(map, visited, i, res, cycle);
        }
        if(cycle) return vector<int>();
        return res;
    }
};

[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;
    }
};