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