1
class UnionFind {
2
    std::vector<int> _parent, _rank;
3

4
public:
5
    UnionFind(int n) : _parent(n), _rank(n, 0) {
6
        std::iota(_parent.begin(), _parent.end(), 0);  // parent[i] = i
7
    }
8

9
    int find(int x) {
10
        if (_parent[x] != x) {
11
            _parent[x] = find(_parent[x]);  // 路径压缩
12
        }
13
        return _parent[x];
14
    }
15

16
    bool unite(int x, int y) {
17
        int rx = find(x), ry = find(y);
18
        if (rx == ry) return false;  // 已连通，不合并
19

20
        // 按秩合并
21
        if (_rank[rx] < _rank[ry]) std::swap(rx, ry);
22
        _parent[ry] = rx;
23
        if (_rank[rx] == _rank[ry]) ++_rank[rx];
24
        return true;  // 合并成功
25
    }
26

27
    bool connected(int x, int y) { return find(x) == find(y); }
28
};

1
#include <vector>
2
#include <algorithm>
3
#include <numeric>
4

5
struct Edge {
6
    int u, v, weight;
7
    bool operator<(const Edge& other) const { return weight < other.weight; }
8
};
9

10
// Kruskal —— 返回 {MST 的总权重, MST 的边集}
11
// 如果图不连通, 返回的边数 < V-1
12
std::pair<int, std::vector<Edge>> kruskal(int n, std::vector<Edge>& edges) {
13
    // 1. 按权重排序
14
    std::sort(edges.begin(), edges.end());
15

16
    // 2. 初始化并查集
17
    UnionFind uf(n);
18

19
    int total_weight = 0;
20
    std::vector<Edge> mst_edges;
21

22
    // 3. 贪心选边
23
    for (const auto& e : edges) {
24
        if (uf.unite(e.u, e.v)) {
25
            // 两端点不在同一连通分量 → 选这条边
26
            total_weight += e.weight;
27
            mst_edges.push_back(e);
28

29
            // 优化: 选够 V-1 条边就可以停了
30
            if (static_cast<int>(mst_edges.size()) == n - 1) break;
31
        }
32
    }
33

34
    return {total_weight, mst_edges};
35
}

1
Prim 算法流程 (从节点 0 出发):
2

3
初始: MST = {0}, 候选边 = 0 的所有邻边
4

5
Step 1: 候选边中最小的 = (0,3,2) → 选 ✓
6
        MST = {0, 3}, 加入 3 的邻边到候选
7

8
Step 2: 候选边中最小的 = (3,1,1) → 选 ✓
9
        MST = {0, 3, 1}, 加入 1 的邻边
10

11
Step 3: 候选边中最小的 = (1,2,3) → 选 ✓
12
        MST = {0, 3, 1, 2}, 加入 2 的邻边
13

14
Step 4: 候选边中最小的 = (2,4,2) → 选 ✓
15
        MST = {0, 3, 1, 2, 4}
16

17
V-1 = 4 条边选完 → MST 完成!
18

19
Prim 的思路: "从已有的岛屿出发, 每次找最便宜的桥连到新节点"

1
#include <vector>
2
#include <queue>
3

4
// Prim —— 邻接表版, 返回 MST 总权重
5
// graph[u] = {{v, w}, ...}
6
int prim(const std::vector<std::vector<std::pair<int,int>>>& graph) {
7
    int n = graph.size();
8
    std::vector<bool> in_mst(n, false);
9
    // 最小堆: {边权, 目标节点}
10
    std::priority_queue<std::pair<int,int>,
11
                        std::vector<std::pair<int,int>>,
12
                        std::greater<>> pq;
13

14
    int total_weight = 0;
15
    int edges_added = 0;
16

17
    // 从节点 0 开始
18
    in_mst[0] = true;
19
    for (auto [v, w] : graph[0]) {
20
        pq.push({w, v});
21
    }
22

23
    while (!pq.empty() && edges_added < n - 1) {
24
        auto [w, u] = pq.top();
25
        pq.pop();
26

27
        if (in_mst[u]) continue;  // 已在 MST 中, 跳过
28

29
        // 纳入 MST
30
        in_mst[u] = true;
31
        total_weight += w;
32
        ++edges_added;
33

34
        // 把 u 的邻边加入候选
35
        for (auto [v, wt] : graph[u]) {
36
            if (!in_mst[v]) {
37
                pq.push({wt, v});
38
            }
39
        }
40
    }
41

42
    return total_weight;
43
}

1
课程依赖图 (DAG):
2
  高数 → 线代 → 机器学习
3
  高数 → 概率论 → 机器学习
4
  编程基础 → 数据结构 → 算法
5

6
合法的拓扑序:
7
  [编程基础, 高数, 数据结构, 线代, 概率论, 算法, 机器学习]
8
  [高数, 编程基础, 线代, 概率论, 数据结构, 机器学习, 算法]
9
  ... (多种合法排列)
10

11
不合法:
12
  [机器学习, 高数, ...]  ← 机器学习依赖高数, 不能排在前面!
13

14
如果图中有环:
15
  A → B → C → A  ← 循环依赖, 不存在拓扑序!

1
图:           入度:
2
  5 → 2       0: 0
3
  5 → 0       1: 0
4
  4 → 0       2: 2 (来自 5,3)
5
  4 → 1       3: 1 (来自 4)
6
  2 → 3       4: 0
7
  3 → 1       5: 0
8

9
Step 1: 入度=0 的入队: [5, 4, 1, 0]  (多个合法起点)
10

11
Step 2: 出队 5 → 排列=[5]
12
        5→2: 入度[2]=1  5→0: 入度[0]已为0且已入队
13

14
Step 3: 出队 4 → 排列=[5,4]
15
        4→0: 入度[0]已处理  4→1: 入度[1]已为0
16
        ... (继续)
17

18
最终: [5, 4, 0, 1, 2, 3] 或其他合法序列

1
#include <vector>
2
#include <queue>
3

4
// Kahn 拓扑排序 —— BFS + 入度
5
// 返回拓扑序列; 如果有环, 返回的序列长度 < n
6
std::vector<int> topological_sort_kahn(
7
    int n, const std::vector<std::vector<int>>& graph)
8
{
9
    // 1. 计算入度
10
    std::vector<int> in_degree(n, 0);
11
    for (int u = 0; u < n; ++u) {
12
        for (int v : graph[u]) {
13
            ++in_degree[v];
14
        }
15
    }
16

17
    // 2. 所有入度为 0 的节点入队
18
    std::queue<int> q;
19
    for (int i = 0; i < n; ++i) {
20
        if (in_degree[i] == 0) {
21
            q.push(i);
22
        }
23
    }
24

25
    // 3. BFS
26
    std::vector<int> topo_order;
27
    while (!q.empty()) {
28
        int u = q.front();
29
        q.pop();
30
        topo_order.push_back(u);
31

32
        for (int v : graph[u]) {
33
            --in_degree[v];
34
            if (in_degree[v] == 0) {
35
                q.push(v);
36
            }
37
        }
38
    }
39

40
    // 4. 如果排出的节点数 < n, 说明有环
41
    // topo_order.size() == n → DAG, 排序成功
42
    // topo_order.size() <  n → 有环, 排序失败
43
    return topo_order;
44
}

1
#include <vector>
2
#include <algorithm>
3

4
// DFS 拓扑排序
5
class TopologicalSortDFS {
6
    std::vector<std::vector<int>> _graph;
7
    std::vector<int> _color;  // 0=WHITE, 1=GRAY, 2=BLACK
8
    std::vector<int> _order;
9
    bool _has_cycle = false;
10

11
    void _dfs(int u) {
12
        if (_has_cycle) return;
13

14
        _color[u] = 1;  // GRAY: 正在访问
15

16
        for (int v : _graph[u]) {
17
            if (_color[v] == 1) {
18
                _has_cycle = true;  // 遇到 GRAY → 环!
19
                return;
20
            }
21
            if (_color[v] == 0) {
22
                _dfs(v);
23
            }
24
        }
25

26
        _color[u] = 2;  // BLACK: 访问完毕
27
        _order.push_back(u);  // 后序: 完成时加入
28
    }
29

30
public:
31
    // 返回拓扑序列; 如果有环, 返回空数组
32
    std::vector<int> sort(int n, const std::vector<std::vector<int>>& graph) {
33
        _graph = graph;
34
        _color.assign(n, 0);
35
        _order.clear();
36
        _has_cycle = false;
37

38
        for (int i = 0; i < n; ++i) {
39
            if (_color[i] == 0) {
40
                _dfs(i);
41
            }
42
        }
43

44
        if (_has_cycle) return {};
45

46
        std::reverse(_order.begin(), _order.end());  // 后序翻转 = 拓扑序
47
        return _order;
48
    }
49
};

1
int minCostConnectPoints(std::vector<std::vector<int>>& points) {
2
    int n = points.size();
3
    std::vector<Edge> edges;
4

5
    // 建完全图的边列表
6
    for (int i = 0; i < n; ++i) {
7
        for (int j = i + 1; j < n; ++j) {
8
            int dist = std::abs(points[i][0] - points[j][0])
9
                     + std::abs(points[i][1] - points[j][1]);
10
            edges.push_back({i, j, dist});
11
        }
12
    }
13

14
    // Kruskal
15
    std::sort(edges.begin(), edges.end());
16

17
    UnionFind uf(n);
18
    int total = 0, count = 0;
19

20
    for (const auto& [u, v, w] : edges) {
21
        if (uf.unite(u, v)) {
22
            total += w;
23
            if (++count == n - 1) break;
24
        }
25
    }
26

27
    return total;
28
}
29
// 时间 O(n² log n), 空间 O(n²)

1
int minCostConnectPoints_prim(std::vector<std::vector<int>>& points) {
2
    int n = points.size();
3
    std::vector<int> min_cost(n, INT_MAX);  // 连接到 MST 的最小代价
4
    std::vector<bool> in_mst(n, false);
5

6
    min_cost[0] = 0;
7
    int total = 0;
8

9
    for (int i = 0; i < n; ++i) {
10
        // 找不在 MST 中的最小 cost 节点
11
        int u = -1;
12
        for (int j = 0; j < n; ++j) {
13
            if (!in_mst[j] && (u == -1 || min_cost[j] < min_cost[u])) {
14
                u = j;
15
            }
16
        }
17

18
        in_mst[u] = true;
19
        total += min_cost[u];
20

21
        // 更新所有非 MST 节点到 MST 的最小代价
22
        for (int v = 0; v < n; ++v) {
23
            if (!in_mst[v]) {
24
                int dist = std::abs(points[u][0] - points[v][0])
25
                         + std::abs(points[u][1] - points[v][1]);
26
                min_cost[v] = std::min(min_cost[v], dist);
27
            }
28
        }
29
    }
30

31
    return total;
32
}
33
// 时间 O(n²), 空间 O(n) —— 比 Kruskal 更优!

1
std::vector<int> findOrder(int numCourses,
2
                           std::vector<std::vector<int>>& prerequisites)
3
{
4
    std::vector<std::vector<int>> graph(numCourses);
5
    std::vector<int> in_degree(numCourses, 0);
6

7
    for (auto& p : prerequisites) {
8
        graph[p[1]].push_back(p[0]);  // p[1] → p[0]
9
        ++in_degree[p[0]];
10
    }
11

12
    std::queue<int> q;
13
    for (int i = 0; i < numCourses; ++i) {
14
        if (in_degree[i] == 0) q.push(i);
15
    }
16

17
    std::vector<int> order;
18
    while (!q.empty()) {
19
        int u = q.front();
20
        q.pop();
21
        order.push_back(u);
22

23
        for (int v : graph[u]) {
24
            if (--in_degree[v] == 0) {
25
                q.push(v);
26
            }
27
        }
28
    }
29

30
    // 有环 → 排出的节点数 < numCourses
31
    return static_cast<int>(order.size()) == numCourses ? order : std::vector<int>{};
32
}
33
// 时间 O(V+E), 空间 O(V+E)

1
Step 1: 理解题意
2
  输入的单词列表是按"外星字典序"排列的
3
  我们要从这个排列顺序中反推出字母的先后关系
4

5
Step 2: 关键观察
6
  两个相邻单词的第一个不同字符, 暗示了字母的偏序
7
  例: words = ["wrt", "wrf"]
8
    → 第一个不同: 't' vs 'f' → 在外星语中 't' < 'f'
9

10
  这就像比较两个中文词的拼音序, 从差异字推导拼音表!
11

12
Step 3: 建模
13
  "字母 A 排在字母 B 前面" → 有向边 A → B
14
  多个这样的偏序关系 → 有向图
15
  求所有字母的总排序 → 拓扑排序!
16

17
Step 4: 边界
18
  - "abc" 排在 "ab" 前面 → 不合法 (短的应该在前)
19
  - 有环 → 不合法
20
  - 多个合法答案 → 任选其一 (Kahn 自然给出一个)

1
std::string alienOrder(std::vector<std::string>& words) {
2
    // 1. 收集所有出现的字符
3
    std::unordered_map<char, std::unordered_set<char>> graph;
4
    std::unordered_map<char, int> in_degree;
5

6
    for (auto& w : words) {
7
        for (char c : w) {
8
            if (graph.find(c) == graph.end()) {
9
                graph[c] = {};
10
                in_degree[c] = 0;
11
            }
12
        }
13
    }
14

15
    // 2. 从相邻单词的第一个不同字符提取偏序
16
    for (int i = 0; i + 1 < static_cast<int>(words.size()); ++i) {
17
        const auto& w1 = words[i];
18
        const auto& w2 = words[i + 1];
19

20
        // 特殊情况: "abc" 在 "ab" 前面 → 不合法
21
        if (w1.size() > w2.size()
22
            && w1.substr(0, w2.size()) == w2)
23
        {
24
            return "";
25
        }
26

27
        int len = std::min(w1.size(), w2.size());
28
        for (int j = 0; j < len; ++j) {
29
            if (w1[j] != w2[j]) {
30
                // w1[j] → w2[j]: w1[j] 排在 w2[j] 前面
31
                if (graph[w1[j]].insert(w2[j]).second) {
32
                    ++in_degree[w2[j]];
33
                }
34
                break;  // 只看第一个不同的字符
35
            }
36
        }
37
    }
38

39
    // 3. Kahn 拓扑排序
40
    std::queue<char> q;
41
    for (auto& [c, deg] : in_degree) {
42
        if (deg == 0) q.push(c);
43
    }
44

45
    std::string result;
46
    while (!q.empty()) {
47
        char c = q.front();
48
        q.pop();
49
        result += c;
50

51
        for (char next : graph[c]) {
52
            if (--in_degree[next] == 0) {
53
                q.push(next);
54
            }
55
        }
56
    }
57

58
    // 有环 → 排出的字符数 < 总字符数
59
    return result.size() == in_degree.size() ? result : "";
60
}
61
// 时间 O(C), C = 所有字符串的总长度

1
std::vector<int> findMinHeightTrees(int n, std::vector<std::vector<int>>& edges) {
2
    if (n == 1) return {0};
3

4
    std::vector<std::unordered_set<int>> adj(n);
5
    for (auto& e : edges) {
6
        adj[e[0]].insert(e[1]);
7
        adj[e[1]].insert(e[0]);
8
    }
9

10
    // 叶节点入队 (度 = 1)
11
    std::queue<int> leaves;
12
    for (int i = 0; i < n; ++i) {
13
        if (adj[i].size() == 1) leaves.push(i);
14
    }
15

16
    int remaining = n;
17
    while (remaining > 2) {
18
        int leaf_count = leaves.size();
19
        remaining -= leaf_count;
20

21
        for (int i = 0; i < leaf_count; ++i) {
22
            int leaf = leaves.front();
23
            leaves.pop();
24

25
            // 删除叶节点及其边
26
            int neighbor = *adj[leaf].begin();
27
            adj[neighbor].erase(leaf);
28

29
            if (adj[neighbor].size() == 1) {
30
                leaves.push(neighbor);  // 新叶节点
31
            }
32
        }
33
    }
34

35
    // 剩余 1 或 2 个节点 = 答案
36
    std::vector<int> result;
37
    while (!leaves.empty()) {
38
        result.push_back(leaves.front());
39
        leaves.pop();
40
    }
41
    return result;
42
}
43
// 时间 O(V), 空间 O(V)

1
int minimumSemesters(int n, std::vector<std::vector<int>>& relations) {
2
    std::vector<std::vector<int>> graph(n + 1);
3
    std::vector<int> in_degree(n + 1, 0);
4

5
    for (auto& r : relations) {
6
        graph[r[0]].push_back(r[1]);
7
        ++in_degree[r[1]];
8
    }
9

10
    std::queue<int> q;
11
    for (int i = 1; i <= n; ++i) {
12
        if (in_degree[i] == 0) q.push(i);
13
    }
14

15
    int semesters = 0, count = 0;
16

17
    while (!q.empty()) {
18
        ++semesters;
19
        int size = q.size();
20

21
        for (int i = 0; i < size; ++i) {
22
            int u = q.front();
23
            q.pop();
24
            ++count;
25

26
            for (int v : graph[u]) {
27
                if (--in_degree[v] == 0) {
28
                    q.push(v);
29
                }
30
            }
31
        }
32
    }
33

34
    return count == n ? semesters : -1;  // -1 = 有环
35
}
36
// 时间 O(V+E), 空间 O(V+E)

1
// RPG 游戏中的技能依赖系统
2
// 技能之间有前置要求: "学了火球术才能学陨石火雨"
3
// 本质: DAG + 拓扑排序
4

5
struct Skill {
6
    int id;
7
    std::string name;
8
    int level_required;
9
    std::vector<int> prerequisites;  // 前置技能 ID
10
    bool unlocked = false;
11
};
12

13
class SkillTree {
14
    std::vector<Skill> _skills;
15
    std::vector<std::vector<int>> _graph;  // 依赖图: prereq → skill
16
    int _n;
17

18
public:
19
    SkillTree(int n) : _n(n), _skills(n), _graph(n) {}
20

21
    void add_dependency(int prereq, int skill) {
22
        _graph[prereq].push_back(skill);
23
        _skills[skill].prerequisites.push_back(prereq);
24
    }
25

26
    // 检查技能是否可学习
27
    bool can_learn(int skill_id) const {
28
        for (int prereq : _skills[skill_id].prerequisites) {
29
            if (!_skills[prereq].unlocked) return false;
30
        }
31
        return true;
32
    }
33

34
    // 获取当前可学习的所有技能 (入度为 0 的未解锁技能)
35
    std::vector<int> available_skills() const {
36
        std::vector<int> result;
37
        for (int i = 0; i < _n; ++i) {
38
            if (!_skills[i].unlocked && can_learn(i)) {
39
                result.push_back(i);
40
            }
41
        }
42
        return result;
43
    }
44

45
    // 验证技能树是否有循环依赖 (开发阶段的完整性检查)
46
    bool validate() const {
47
        auto topo = topological_sort_kahn(_n, _graph);
48
        return static_cast<int>(topo.size()) == _n;
49
    }
50

51
    // 计算到学会目标技能的最短路径 (需要学多少个前置技能)
52
    std::vector<int> learning_path(int target) const {
53
        // 反向 BFS: 从 target 出发, 找到所有必须先学的技能
54
        std::vector<bool> needed(_n, false);
55
        std::queue<int> q;
56
        q.push(target);
57
        needed[target] = true;
58

59
        while (!q.empty()) {
60
            int s = q.front();
61
            q.pop();
62
            for (int prereq : _skills[s].prerequisites) {
63
                if (!needed[prereq] && !_skills[prereq].unlocked) {
64
                    needed[prereq] = true;
65
                    q.push(prereq);
66
                }
67
            }
68
        }
69

70
        // 对 "needed" 子图做拓扑排序 → 学习顺序
71
        std::vector<int> path;
72
        // ... (拓扑排序, 只包含 needed=true 的节点)
73
        return path;
74
    }
75
};
76

77
// 使用示例:
78
// SkillTree tree(10);
79
// tree.add_dependency(FIREBALL, METEOR);        // 火球术 → 陨石
80
// tree.add_dependency(FIREBALL, FIRE_WALL);     // 火球术 → 火墙
81
// tree.add_dependency(FIRE_WALL, INFERNO);      // 火墙 → 地狱火
82
// tree.add_dependency(METEOR, INFERNO);          // 陨石 → 地狱火
83
//
84
// auto avail = tree.available_skills();  // 当前可学: [FIREBALL, ICE_BOLT, ...]

1
// 游戏启动时, 资源之间有加载依赖
2
// Shader 编译 → Material 创建 → Mesh 渲染
3
// 纹理加载 → Material 创建
4
// 本质: DAG 拓扑排序, 确定加载顺序; 层级信息 → 并行加载
5

6
struct Resource {
7
    std::string name;
8
    std::string type;  // "texture", "shader", "material", "mesh"
9
};
10

11
class ResourceLoader {
12
    int _n;
13
    std::vector<Resource> _resources;
14
    std::vector<std::vector<int>> _deps;  // deps[i] = i 依赖的资源
15

16
public:
17
    // 用 Kahn 拓扑排序, 确定加载顺序
18
    // 同一层的资源可以**并行**加载!
19
    std::vector<std::vector<int>> get_loading_batches() {
20
        std::vector<int> in_degree(_n, 0);
21
        std::vector<std::vector<int>> graph(_n);
22

23
        for (int i = 0; i < _n; ++i) {
24
            for (int dep : _deps[i]) {
25
                graph[dep].push_back(i);
26
                ++in_degree[i];
27
            }
28
        }
29

30
        std::queue<int> q;
31
        for (int i = 0; i < _n; ++i) {
32
            if (in_degree[i] == 0) q.push(i);
33
        }
34

35
        std::vector<std::vector<int>> batches;
36
        while (!q.empty()) {
37
            std::vector<int> batch;
38
            int size = q.size();
39

40
            for (int i = 0; i < size; ++i) {
41
                int r = q.front();
42
                q.pop();
43
                batch.push_back(r);
44

45
                for (int next : graph[r]) {
46
                    if (--in_degree[next] == 0) {
47
                        q.push(next);
48
                    }
49
                }
50
            }
51

52
            batches.push_back(std::move(batch));
53
        }
54

55
        return batches;
56
        // batches[0] = 无依赖, 先加载 (并行)
57
        // batches[1] = 依赖 batch 0 的, 再加载 (并行)
58
        // ...
59
    }
60
};
61

62
// 实际效果:
63
// Batch 0: [base_shader, stone_texture, wood_texture]  ← 并行加载
64
// Batch 1: [wall_material, floor_material]              ← 依赖 batch 0
65
// Batch 2: [level_mesh]                                 ← 依赖 batch 1
66
// 总加载时间 = max(batch时间) 之和, 远优于串行加载

1
// Roguelike 地图生成: 随机放置房间, 用 MST 保证连通
2
// 步骤:
3
// 1. 随机生成 N 个房间的中心点
4
// 2. 所有房间之间建完全图 (距离 = 曼哈顿/欧几里得)
5
// 3. Kruskal 求 MST → 保证所有房间互通
6
// 4. 随机额外添加几条非 MST 边 → 增加路径多样性
7
// 5. 沿选中的边挖走廊
8

9
struct Room {
10
    int cx, cy;   // 中心坐标
11
    int width, height;
12
};
13

14
class DungeonGenerator {
15
public:
16
    struct Corridor {
17
        int room_a, room_b;
18
    };
19

20
    std::vector<Corridor> generate_corridors(const std::vector<Room>& rooms) {
21
        int n = rooms.size();
22

23
        // 1. 建完全图的边列表
24
        std::vector<Edge> edges;
25
        for (int i = 0; i < n; ++i) {
26
            for (int j = i + 1; j < n; ++j) {
27
                int dist = std::abs(rooms[i].cx - rooms[j].cx)
28
                         + std::abs(rooms[i].cy - rooms[j].cy);
29
                edges.push_back({i, j, dist});
30
            }
31
        }
32

33
        // 2. Kruskal 求 MST
34
        std::sort(edges.begin(), edges.end());
35
        UnionFind uf(n);
36

37
        std::vector<Corridor> corridors;
38
        std::vector<Edge> non_mst;
39

40
        for (const auto& e : edges) {
41
            if (uf.unite(e.u, e.v)) {
42
                corridors.push_back({e.u, e.v});  // MST 边 → 必要走廊
43
            } else {
44
                non_mst.push_back(e);  // 非 MST 边
45
            }
46
        }
47

48
        // 3. 随机添加 10-20% 的额外走廊 (增加路径多样性)
49
        int extra = std::max(1, static_cast<int>(non_mst.size()) / 5);
50
        // 随机选 extra 条非 MST 边加入
51
        std::shuffle(non_mst.begin(), non_mst.end(),
52
                     std::mt19937{std::random_device{}()});
53
        for (int i = 0; i < extra && i < static_cast<int>(non_mst.size()); ++i) {
54
            corridors.push_back({non_mst[i].u, non_mst[i].v});
55
        }
56

57
        return corridors;
58
    }
59
};
60

61
// 结果:
62
// MST 走廊保证所有房间可达 (不会有死角)
63
// 额外走廊增加分支路径 (玩家体验更好)
64
// 这是 Roguelike 游戏中最经典的地图生成算法之一

1
// MMO 的任务系统: 任务之间有前置关系
2
// "完成主线 1-3 才能接主线 4"
3
// "完成支线 A 和 B 才能接隐藏任务"
4

5
struct Quest {
6
    int id;
7
    std::string name;
8
    std::vector<int> prerequisites;
9
    bool completed = false;
10
};
11

12
class QuestManager {
13
    std::vector<Quest> _quests;
14

15
public:
16
    // 玩家当前可接的任务 = 入度为 0 的未完成任务
17
    std::vector<int> available_quests() const {
18
        std::vector<int> result;
19
        for (const auto& q : _quests) {
20
            if (q.completed) continue;
21
            bool all_prereq_done = true;
22
            for (int p : q.prerequisites) {
23
                if (!_quests[p].completed) {
24
                    all_prereq_done = false;
25
                    break;
26
                }
27
            }
28
            if (all_prereq_done) result.push_back(q.id);
29
        }
30
        return result;
31
    }
32

33
    // 完成任务 → 可能解锁新任务
34
    std::vector<int> complete_quest(int quest_id) {
35
        _quests[quest_id].completed = true;
36
        return available_quests();  // 返回新的可接任务列表
37
    }
38

39
    // 估算完成某个目标任务需要做多少个前置任务
40
    // = 从目标任务反向 BFS 到所有未完成的前置
41
    int estimate_effort(int target) const {
42
        std::unordered_set<int> needed;
43
        std::queue<int> q;
44
        q.push(target);
45

46
        while (!q.empty()) {
47
            int cur = q.front();
48
            q.pop();
49
            for (int p : _quests[cur].prerequisites) {
50
                if (!_quests[p].completed && needed.insert(p).second) {
51
                    q.push(p);
52
                }
53
            }
54
        }
55
        return needed.size();
56
    }
57
};