Courses Schedule II

發表於   |   分類於

Courses Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

拓扑排序。流程和 Courses Schedule一样。但有两个需要注意的地方：

  • pair是边，如果没有边的话，那么所有的节点都是单独的，因此应当按照编号输出所有节点；
  • 如果没有可行的选课方案，那么最后的最后的选课的队列长度一定不等于课程数目，从而能可以判定无解，清空选课队列并输出。
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
class Solution {
public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<int> order;
		if (numCourses == 0) return order;
		int reqs = prerequisites.size();
		if (reqs == 0)
		{
		    for (int i = 0; i < numCourses; ++i)
		    {
		        order.push_back(i);
		    }
		    return order;
		}
		vector<int> inDegrees(numCourses, 0);
		vector<vector<int>> graphic(numCourses, vector<int>());
		for (auto p : prerequisites)
		{
			graphic[p.second].push_back(p.first);
			inDegrees[p.first]++;
		}
		queue<int> q;
		for (int i = 0; i < numCourses; ++i)
		{
			if (inDegrees[i] == 0)
			{
				q.push(i);
				order.push_back(i);
			}
		}

		while (!q.empty())
		{
			int f = q.front();
			q.pop();
			for (auto i = 0; i < graphic[f].size(); ++i)
			{
				inDegrees[graphic[f][i]]--;
				if (inDegrees[graphic[f][i]] == 0)
				{
					q.push(graphic[f][i]);
					order.push_back(graphic[f][i]);
				}
			}
		}
		if (order.size() != numCourses) order.clear();
		return order;
	}
};