启动多任务排序 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。

现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。

例如: B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是:A任务，E任务，B任务，C任务，D任务。这里A和E任务都是没有依赖的，立即执行。

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号”->”表示依赖方向。

例如A->B表示A依赖B，多个依赖之间用单个空格分割

输出描述

输出为排序后的启动任务列表，多个任务之间用单个空格分割

示例1

输入：
A->B C->B

输出：
B A C

题解

这是一个典型的拓扑排序问题，通过建立任务之间的依赖关系图，然后按照一定规则执行任务，即先执行没有依赖的任务，然后再执行依赖于前面任务的任务。

以下是解题思路和代码大致描述：

1. 使用两个字典，outdegree用于记录每个任务的出度（依赖它的任务数量），depend用于记录每个任务依赖的任务列表。
2. 遍历输入的任务依赖关系，构建任务之间的依赖图，并同时维护出度信息。
3. 利用拓扑排序的思想，循环执行以下步骤：
   • 找到出度为0的任务，如果存在多个，按字母顺序排序。
   • 将该任务加入结果集，并标记该任务已遍历。
   • 更新邻居任务的出度，将它们的出度减1。
   • 重复上述步骤，直到所有任务都被遍历。

代码使用了相应的数据结构和算法来实现这一过程，并输出最终排序后的启动任务列表。

时间复杂度：O(N + MlogM)，其中N是任务数量，M是依赖关系数量。建图和拓扑排序的过程时间复杂度为O(N + M)，排序的时间复杂度为O(MlogM)。 空间复杂度：O(N + M)，存储了任务的出度信息和依赖关系。

Java

import java.util.*;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Map<String, Integer> outdegree = new HashMap<>();
        Map<String, List<String>> depend = new HashMap<>();

        Scanner scanner = new Scanner(System.in);
        String[] relations = scanner.nextLine().split(" ");

        // 建立依赖关系，维护出度
        for (String relation : relations) {
            // a 依赖 b
            String[] parts = relation.split("->");
            String a = parts[0];
            String b = parts[1];

            depend.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            outdegree.putIfAbsent(a, 0);
            outdegree.putIfAbsent(b, 0);
            outdegree.put(a, outdegree.get(a) + 1);
        }

        // 拓扑排序结果
        List<String> rs = new ArrayList<>();
        while (true) {
            // 找到出度为0的节点，并将其加入结果集中
            List<String> temp = new ArrayList<>();