《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（42）九龙神火罩拓扑 - 课程表排序（拓扑排序）

《灵珠觉醒：从零到算法金仙的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。