面试经典150题 P207 课程表

---

时间轴

时间轴

2025-11-04

init

拓扑排序

---

题目：

P207 课程表

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

先是用 DFS 发现会WA，原因是如果存在环，DFS 遍历是能成功的。

#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;
		// =======建图==========
		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;
		}

		// 查找所有入度为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;
	}
};

拓扑排序

每次移除入度为 0 的节点(使用队列或栈保存当前入度为 0 的结点，然后让当队列或栈中所有结点的 neighbor 的入度-1，如果减一后变为 0 则加入队列或栈)

#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; // 若有环，则 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)
        {
                // 建图
                int i;
                vector<vector<int> > graph(numCourses);
                vector<int> indegree(numCourses, 0); // 保存每个节点的入度
                vector<bool> pushed(numCourses, false);
                queue<int> que;

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

                // 拓扑排序
                // 初始化先把入度为0的边加入
                for (i = 0; i < numCourses; i++) {
                        if (indegree[i] == 0) {
                                que.push(i);
                                pushed[i] = true;
                        }
                }

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

                        // 每次找入度为 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;
        }
};