时间轴

2025-11-04

init

题目：

P210 课程表 II

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

拓扑排序

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
#include <vector>
#include <unordered_map>
#include <queue>

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

class Solution {
    public:
	vector<int> findOrder(int numCourses,
			      vector<vector<int> > &prerequisites)
	{
		unordered_map<int, vector<int> > graph;
		unordered_map<int, int> indegree;
		// =====建图======
		int i, n = prerequisites.size();

		for (i = 0; i < numCourses; i++) {
			graph[i] = vector<int>();
			indegree[i] = 0;
		}

		int curr, prev;

		for (i = 0; i < n; i++) {
			curr = prerequisites[i][0];
			prev = prerequisites[i][1];
			graph[prev].push_back(curr);
			indegree[curr] += 1;
		}
		// 拓扑排序
		int p;
		vector<int> order;
		queue<int> que;
		for (i = 0; i < numCourses; i++) {
			if (indegree[i] == 0) {
				que.push(i);
			}
		}

		while (!que.empty()) {
			p = que.front();
			que.pop();
			order.push_back(p);
			for (auto val : graph[p]) {
				indegree[val] --;
				if(indegree[val] == 0){
				    que.push(val);
				}
			}
		}
		if(order.size() == numCourses){
		    return order;
		}
		return vector<int>();
	}
};