Interview Classic 150 Questions P207 Course Schedule

---

Timeline

Timeline

2025-11-04

init

Topological Sort

---

Problem:

P207 Course Schedule

https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-interview-150

First, using DFS, it will be found thatWA, the reason is that if there is a cycle, DFS traversal can succeed.

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>

using std::vector;
using std::unordered_map;
using std::unordered_set;
using std::stack;

class Solution {
    public:
	bool canFinish(int numCourses, vector<vector<int> > &prerequisites)
	{
		// node -> neighbor
		unordered_map<int, vector<int> > graph;
		// node -> prev count
		unordered_map<int, int> prev_count;

		int i, n = prerequisites.size();
		if (n == 0) {
			return true;
		}

		int prev, curr;
		// =======Build Graph==========
		for (i = 0; i < numCourses; i++) {
			graph[i] = vector<int>();
			prev_count[i] = 0;
		}
		for (i = 0; i < n; i++) {
			curr = prerequisites[i][0];
			prev = prerequisites[i][1];

			graph[prev].push_back(curr);
			prev_count[curr] += 1;
		}

		// Find all nodes with indegree 0
		vector<int> start_vec;
		for (auto it = prev_count.begin(); it != prev_count.end();
		     it++) {
			if (it->second == 0) {
				start_vec.push_back(it->first);
			}
		}

		// ========DFS==========
		unordered_set<int> visited;
		n = start_vec.size();
		int p;

		for (i = 0; i < n; i++) {
			stack<int> st;

			if (!visited.count(start_vec[i])) {
				st.push(start_vec[i]);
			}

			while (!st.empty()) {
				p = st.top();
				st.pop();

				if (visited.count(p) != 0) {
					continue;
				}
				visited.insert(p);

				for (int node : graph[p]) {
					if (!visited.count(node)) {
						st.push(node);
					}
				}
			}
		}
		return visited.size() == numCourses;
	}
};

Topological Sort

Each time remove a node with indegree 0 (use a queue or stack to store nodes with indegree 0, then decrement the indegree of all neighbors of nodes in the queue or stack by 1; if the indegree becomes 0 after decrement, add it to the queue or stack)

#include <vector>
#include <queue>
using std::vector;
using std::queue;

class Solution {
    public:
	bool canFinish(int numCourses, vector<vector<int> > &prerequisites)
	{
		vector<vector<int> > graph(numCourses);
		vector<int> indegree(numCourses, 0);

		for (auto &pre : prerequisites) {
			graph[pre[1]].push_back(pre[0]);
			indegree[pre[0]]++;
		}

		queue<int> q;
		for (int i = 0; i < numCourses; i++) {
			if (indegree[i] == 0) {
				q.push(i);
			}
		}

		int visited = 0;
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			visited++;
			for (int neighbor : graph[node]) {
				indegree[neighbor]--;
				if (indegree[neighbor] == 0) {
					q.push(neighbor);
				}
			}
		}

		return visited == numCourses; // If there is a cycle, then visited < numCourses
	}
};

leetcode hot 100 rewrite

#include <vector>
#include <queue>

using std::vector;
using std::queue;

class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int> > &prerequisites)
        {
                // Build graph
                int i;
                vector<vector<int> > graph(numCourses);
                vector<int> indegree(numCourses, 0); // Save the in-degree of each node
                vector<bool> pushed(numCourses, false);
                queue<int> que;

                for (vector<int> &vec : prerequisites) {
                        graph[vec[1]].push_back(vec[0]);
                        indegree[vec[0]]++;
                }

                // Topological sort
                // Initialize by adding edges with in-degree 0 first
                for (i = 0; i < numCourses; i++) {
                        if (indegree[i] == 0) {
                                que.push(i);
                                pushed[i] = true;
                        }
                }

                while (!que.empty()) {
                        i = que.front();
                        que.pop();

                        // Each time find an edge with in-degree 0
                        for (int course : graph[i]) {
                                indegree[course]--;

                                if (!pushed[course] && indegree[course] == 0) {
                                        que.push(course);
                                        pushed[course] = true;
                                }
                        }
                }

                for (i = 0; i < numCourses; i++) {
                        if (!pushed[i])
                                return false;
                }

                return true;
        }
};