The trick here is to name the state correctly, then let the implementation follow. For 207. Course Schedule, the solution in this repository is mainly a graph traversal solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal.
The notes already sitting in the source point us in the right direction:
- https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isCyclicUtil, canFinish, visited, recStack, incomingEdgeCount.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
02//Runtime: 24 ms, faster than 64.54% of C++ online submissions for Course Schedule.
03//Memory Usage: 12.7 MB, less than 100.00% of C++ online submissions for Course Schedule.
04class Solution {
05public:
06 bool isCyclicUtil(int cur, unordered_map<int, vector<int>>& edges, vector<bool>& visited, vector<bool>& recStack){
07 visited[cur] = true;
08 recStack[cur] = true;
09
10 /*
11 3
12 [[0,1],[0,2],[1,2]]
13 (according to the problem description, the edge is represented as [dst, src])
14 In the example:
15 there are two paths :
16 2->0
17 2->1->0
18 If we go through the first path first, 0 will be marked as visited,
19 later when we go through the second path, we will see 0 as visited,
20 if we only use "visited" to detect cycle, it will fail in this case,
21 so we need "recStack" to check if 0 is on our path
22 */
23
24 for(int nei : edges[cur]){
25 // cout << cur << " -- " << nei << endl;
26 /*
27 the first part can be written as:
28 if(!visited[nei] && isCyclicUtil(nei, edges, visited, recStack))
29 because in the second part, if recStack[nei] is true,
30 then visited[nei] must be true, so it will skip first part anyway
31 */
32 if(!visited[nei]){
33 //find whether its neighbor is cyclic
34 if(isCyclicUtil(nei, edges, visited, recStack)){
35 return true;
36 }
37 }else if(recStack[nei]){
38 //that means nei is both cur's ancestor and its descendent
39 // cout << cur << " -- " << nei << ", nei in recStack" << endl;
40 return true;
41 }
42 }
43
44 //recStack is restored(because we finish this layer of recursion)
45 recStack[cur] = false;
46
47 //Note that visited[cur] is not restored
48
49 return false;
50 };
51
52 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
53 vector<bool> visited(numCourses, false);
54 vector<bool> recStack(numCourses, false);
55
56 bool hasCycle = false;
57
58 unordered_map<int, vector<int>> edges;
59 for(vector<int>& pre : prerequisites){
60 /*
61 this is correct according to the problem definition
62 pre[1] should be taken before pre[0],
63 so the edge is from pre[1] to pre[0]
64 */
65 edges[pre[1]].push_back(pre[0]);
66 //however this also gives correct answer
67 // edges[pre[0]].push_back(pre[1]);
68 }
69
70 for(int i = 0; i < numCourses; i++){
71 if(!visited[i]){
72 if(isCyclicUtil(i, edges, visited, recStack)){
73 //we have cycle
74 hasCycle = true;
75 break;
76 }
77 }
78 }
79
80 return !hasCycle;
81 }
82};
83
84//topological sort, bfs
85//https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java
86//Runtime: 24 ms, faster than 64.54% of C++ online submissions for Course Schedule.
87//Memory Usage: 10.8 MB, less than 100.00% of C++ online submissions for Course Schedule.
88class Solution {
89public:
90 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
91 vector<int> incomingEdgeCount(numCourses, 0);
92 vector<vector<int>> edges(numCourses);
93
94 for(vector<int>& pre : prerequisites){
95 //pre[1] points to pre[0](pre[1] should be taken before pre[0])
96 incomingEdgeCount[pre[0]]++;
97 edges[pre[1]].push_back(pre[0]);
98 }
99
100 queue<int> noIncomingEdges;
101 for(int i = 0; i < numCourses; i++){
102 if(incomingEdgeCount[i] == 0){
103 noIncomingEdges.push(i);
104 }
105 }
106
107 int remainingEdgeCount = prerequisites.size();
108 while(!noIncomingEdges.empty()){
109 int cur = noIncomingEdges.front(); noIncomingEdges.pop();
110 for(int nei : edges[cur]){
111 remainingEdgeCount--;
112 if(--incomingEdgeCount[nei] == 0){
113 noIncomingEdges.push(nei);
114 }
115 }
116 }
117 //if there are redundant edges, there is a cycle
118 return remainingEdgeCount == 0;
119 }
120};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.