时间轴

2025-11-04

init

题目：

P207 课程表

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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 则加入队列或栈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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
	}
};