刷题笔记合集🔗

启动多任务排序

问题描述

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

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

例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：

A任务，E任务，B任务，C任务，D任务

这里A和E任务都是没有依赖的，立即执行。

输入格式

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

A->B：表示A依赖B

多个依赖之间用单个空格分隔。

输出格式

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

样例输入

A->B C->B

样例输出

B A C

数据范围

• 任务名称为非空字符串
• 任务依赖关系不会出现循环依赖

题解

这道题目本质上是一个拓扑排序问题，其中涉及到有向图的构建和遍历。

在拓扑排序中，我们需要按照依赖关系确定任务的执行顺序，确保任务只有在其所有依赖任务都完成后才执行。本题的关键点在于理解依赖关系的表示方式和排序策略。

题目中的表示方法是"A->B"表示A依赖B，也就是说B必须在A之前完成。这与常见的拓扑排序中父节点指向子节点的表示方式是一致的。

解题步骤如下：

1. 构建有向图：对于每个"A->B"关系，B是A的前驱任务，A是B的后继任务
2. 计算每个任务的入度（依赖任务的数量）
3. 将所有入度为0的任务（没有依赖的任务）加入队列
4. 当队列不为空时：
   • 将队列按照任务名称字母顺序排序
   • 出队任务并加入结果列表
   • 对于该任务的所有后继任务，减少其入度
   • 如果任务的入度变为0，将其加入新队列
5. 重复步骤4，直到队列为空

值得注意的是，题目要求同时可执行的多个任务按照字母顺序排序。这意味着我们需要在每一轮处理入度为0的任务前，先对队列进行排序。

时间复杂度分析：

• 构建图和计算入度的时间复杂度为O(E)，其中E是边的数量，即依赖关系的数量
• 排序的时间复杂度为O(V·log(V))，其中V是节点的数量，即任务的数量
• 总体时间复杂度为O(E + V·log(V))

这个算法对于题目给出的数据范围是足够高效的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 解析输入的依赖关系
relations = [rel.split("->") for rel in input().split()]

# 构建图和计算入度
in_degree = {}
next_tasks = {}

# 对于每一个依赖关系A->B，A依赖B
for a, b in relations:
    # 初始化入度
    in_degree[b] = in_degree.get(b, 0)  # B的入度不变
    in_degree[a] = in_degree.get(a, 0) + 1  # A的入度+1
    
    # 初始化后继任务列表
    next_tasks.setdefault(b, []).append(a)  # B的后继任务添加A
    next_tasks.setdefault(a, [])  # 确保A有后继任务列表，即使为空
    
# 拓扑排序
def topo_sort():
    # 找出所有入度为0的任务
    queue = [task for task in in_degree if in_degree[task] == 0]
    result = []
    
    while queue:
        # 按任务名称字母顺序排序
        queue.sort()
        
        # 处理当前层的所有可执行任务
        new_queue = []
        for task in queue:
            result.append(task)
            
            # 更新后继任务的入度
            for next_task in next_tasks[task]:
                in_degree[next_task] -= 1
                
                # 如果入度变为0，加入新队列
                if in_degree[next_task] == 0:
                    new_queue.append(next_task)
        
        queue = new_queue
    
    return result

# 执行拓扑排序并输出结果
result = topo_sort()
print(" ".join(result))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    
    // 解析输入的依赖关系
    stringstream ss(line);
    string relation;
    vector<pair<string, string>> relations;
    
    while (ss >> relation) {
        size_t pos = relation.find("->");
        string a = relation.substr(0, pos);
        string b = relation.substr(pos + 2);
        relations.push_back({a, b});
    }
    
    // 构建图和计算入度
    unordered_map<string, int> in_degree;
    unordered_map<string,