《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(42)九龙神火罩拓扑 - 课程表排序(拓扑排序)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的九龙神火罩大阵,阵中有一座巨大的九龙神火罩,罩身闪烁着神秘的光芒。大阵入口处有一块巨大的石碑,上面刻着一行文字:“欲破此阵,需以九龙神火罩之力,拓扑排序,课程表显真身。”
哪吒定睛一看,石碑上还有一行小字:“课程表[[1, 0], [2, 0], [3, 1], [3, 2]]
的拓扑排序结果为[0, 1, 2, 3]
。”哪吒心中一动,他知道这是一道关于拓扑排序的难题,需要通过拓扑排序的方法,解决课程表的依赖问题。
暴力解法:九龙神火罩的初次尝试
哪吒心想:“要解决课程表排序,我可以尝试所有可能的课程顺序。”他催动九龙神火罩之力,通过递归的方式,枚举所有可能的课程排列,检查是否满足依赖关系。
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
for (auto& pre : prerequisites) {
adj[pre[1]].push_back(pre[0]);
}
vector<int> result;
vector<bool> visited(numCourses, false);
for (int i = 0; i < numCourses; ++i) {
if (!visited[i]) {
if (!dfs(adj, visited, result, i)) {
return {
};
}
}
}
reverse(result.begin(), result.end());
return result;
}
bool dfs(vector<vector<int>>& adj, vector<bool>& visited, vector<int>& result, int node) {
if (visited[node]) return false;
visited[node] = true;
for (int neighbor : adj[node]) {
if (!dfs(adj, visited, result, neighbor)) {
return false;
}
}
result.push_back(node);
return true;
}
哪吒成功地找到了课程表的拓扑排序,但九龙神火罩的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当课程数量很多时,灵力消耗巨大。
C++语法点
在C++中,拓扑排序涉及到图的表示和深度优先搜索。以下是一些重要特性:
图的表示:
- 使用邻接表表示图,每个节点的邻接节点存储在一个列表中。
- 常用操作:
vector<vector<int>> adj(numCourses)
:创建邻接表。adj[u].push_back(v)
:添加有向边u -> v
。