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

发布于:2025-03-15 ⋅ 阅读:(14) ⋅ 点赞:(0)

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

网站公告

今日签到

点亮在社区的每一天
去签到