题解

题面描述

在一个应用启动时，通常需要执行多个初始化任务。这些任务之间可能存在依赖关系，例如，如果任务 A 依赖于任务 B，则必须在任务 B 执行完成后，才能开始执行任务 A。

任务依赖关系规则：

• 每个依赖关系表示为 A->B，表示任务 A 依赖于任务 B。
• 多个依赖关系之间使用单个空格分隔。

任务执行策略（贪婪策略）：

1. 无依赖任务优先：如果一个任务没有任何未完成的依赖任务，则立即开始执行该任务。
2. 字母顺序优先：如果同时有多个任务可以执行，则优先执行任务名称字母顺序较前的任务。

目标：根据给定的任务依赖关系，输出符合上述策略的任务执行顺序，任务之间用单个空格分隔。

思路

本题可以转化为 拓扑排序（Topological Sorting）的问题，即在有向无环图（DAG）中找到一个线性序列，使得对于每一条有向边 U → V，V 在序列中出现在 U 的前面。

为了满足题目中的 贪婪策略 和 字母顺序优先，在拓扑排序的过程中，需要：

1. 选择可执行任务时，优先选择字母序最小的任务。
2. 一次处理所有当前可执行的任务，并按字母顺序执行。

具体步骤如下：

1. 构建图结构：

   • 使用邻接表表示任务之间的依赖关系。
   • 统计每个任务的入度（即有多少任务依赖于它）。

2. 初始化可执行任务：

   • 将所有入度为零的任务（即没有依赖的任务）加入队列，并按字母顺序排序。

3. 执行拓扑排序：

   • 从队列中依次取出任务，添加到执行序列中。
   • 对于该任务的所有邻接任务，减少它们的入度。如果入度变为零，则将它们加入新的一层队列。
   • 新的一层队列同样按字母顺序排序，继续执行。

4. 输出结果：

   • 当所有任务都被执行完毕后，输出执行序列。
   • 如果存在循环依赖（即图中有环），则无法完成所有任务的执行，输出为空。

cpp

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

int main() {
    // 存储每个任务的入度
    map<string, int> inDegree;
    // 存储每个任务的邻接任务
    map<string, vector<string>> nextTasks;

    string dependency;
    // 读取所有依赖关系
    while (cin >> dependency) {
        auto pos = dependency.find("->");
        if (pos == string::npos) continue; // 无效格式，跳过

        // A依赖B，即B执行完才能执行A
        string taskA = dependency.substr(0, pos);
        string taskB = dependency.substr(pos + 2);

        // 初始化任务的入度
        if (inDegree.find(taskB) == inDegree.end()) {
            inDegree[taskB] = 0;
        }
        if (inDegree.find(taskA) == inDegree.end()) {
            inDegree[taskA] = 0;
        }

        // A的入度增加1
        inDegree[taskA]++;

        // 构建邻接表，B指向A
        nextTasks[taskB].push_back(taskA);
    }

    // 队列用于存储当前可执行的任务
    deque<string> queue;
    // 收集所有入度为0的任务
    for (const auto &pair : inDegree) {
        if (pair.second == 0) {
            queue.push_back(pair.first);
        }
    }

    // 结果列表
    vector<string> result;

    while (!queue.empty()) {
        // 将当前层的任务排序
        vector<string> currentLayer(queue.begin(), queue.end());
        sort(currentLayer.begin(), currentLayer.end());

        // 清空当前队列
        queue.clear();

        // 依次处理当前层的任务
        for (const auto &currentTask : currentLayer) {
            // 添加到结果列表
            result.push_back(currentTask);

            // 遍历所有依赖于当前任务的后续任务
            for (const auto &dependentTask : nextTasks[currentTask]) {
                // 当前任务执行完，后续任务的入度减少1
                inDegree[dependentTask]--;

                // 如果后续任务的入度变为0，则加入新队列
                if (inDegree[dependentTask] == 0) {
                    queue.push_back(dependentTask);
                }
            }
        }
    }

    // 检查是否所有任务都被执行
    if (result.size() != inDegree.size()) {
        // 存在循环依赖，无法完成排序，输出为空
        cout << "";
        return 0;
    }

    // 输出结果，任务之间用单个空格分隔
    for(int i = 0; i < result.size(); i++) {
        if(i != 0) cout << " ";
        cout << result[i];
    }
    cout << endl;

    return 0;
}

python

import sys
from collections import defaultdict, deque

def main():
    # 读取所有输入并分割
    input_line = sys.stdin.read().strip()
    dependencies = input_line.split()
    
    # 存储每个任务的入度
    inDegree = defaultdict(int)
    # 存储每个任务的邻接任务
    nextTasks = defaultdict(list)
    # 存储所有任务
    tasks = set()
    
    for dep in dependencies:
        if '->' not in dep:
            continue  # 无效格式，跳过
        taskA, taskB = dep.split('->')
        tasks.add(taskA)
        tasks.add(taskB)
        # A依赖B，故B指向A
        nextTasks[taskB].append(taskA)
        inDegree[taskA] += 1
        # 确保B在入度表中
        if taskB not in inDegree:
            inDegree[taskB] = 0
    
    # 队列用于存储当前可执行的任务
    queue = deque()
    # 收集所有入度为0的任务
    for task in tasks:
        if inDegree[task] == 0:
            queue.append(task)
    
    result = []
    
    while queue:
        # 将当前层的任务排序
        currentLayer = sorted(queue)
        # 清空当前队列
        queue = deque()
        
        for currentTask in currentLayer:
            # 添加到结果列表
            result.append(currentTask)
            
            # 遍历所有依赖于当前任务的后续任务
            for dependentTask in nextTasks[currentTask]:
                # 当前任务执行完，后续任务的入度减少1
                inDegree[dependentTask] -= 1
                # 如果后续任务的入度变为0，则加入新队列
                if inDegree[dependentTask] == 0:
                    queue.append(dependentTask)
     
    # 输出结果，任务之间用单个空格分隔
    print(' '.join(result))

if __name__ == "__main__":
    main()

java

import java.util.*;  
 
public class Main { 
    public static void main(String[] args) { 
        // 存储每个任务的入度 
        Map<String, Integer> inDegree = new HashMap<>(); 
        // 存储每个任务的邻接任务 
        Map<String, List<String>> nextTasks = new HashMap<>(); 
 
        Scanner sc = new Scanner(System.in);  
        // 读取所有依赖关系 
        while (sc.hasNext())  { 
            String dependency = sc.next();  
            int pos = dependency.indexOf("->");  
            if (pos == -1) continue; // 无效格式，跳过 
 
            // A依赖B，即B执行完才能执行A 
            String taskA = dependency.substring(0,  pos); 
            String taskB = dependency.substring(pos  + 2); 
 
            // 初始化任务的入度 
            inDegree.putIfAbsent(taskB,  0); 
            inDegree.putIfAbsent(taskA,  0); 
 
            // A的入度增加1 
            inDegree.put(taskA,  inDegree.get(taskA)  + 1); 
 
            // 构建邻接表，B指向A 
            nextTasks.computeIfAbsent(taskB,  k -> new ArrayList<>()).add(taskA); 
        } 
 
        // 队列用于存储当前可执行的任务 
        Deque<String> queue = new ArrayDeque<>(); 
        // 收集所有入度为0的任务 
        for (Map.Entry<String, Integer> entry : inDegree.entrySet())  { 
            if (entry.getValue()  == 0) { 
                queue.add(entry.getKey());  
            } 
        } 
 
        // 结果列表 
        List<String> result = new ArrayList<>(); 
 
        while (!queue.isEmpty())  { 
            // 将当前层的任务排序 
            List<String> currentLayer = new ArrayList<>(queue); 
            Collections.sort(currentLayer);  
 
            // 清空当前队列 
            queue.clear();  
 
            // 依次处理当前层的任务 
            for (String currentTask : currentLayer) { 
                // 添加到结果列表 
                result.add(currentTask);  
 
                // 遍历所有依赖于当前任务的后续任务 
                if (nextTasks.containsKey(currentTask))  { 
                    for (String dependentTask : nextTasks.get(currentTask))  { 
                        // 当前任务执行完，后续任务的入度减少1 
                        inDegree.put(dependentTask,  inDegree.get(dependentTask)  - 1); 
 
                        // 如果后续任务的入度变为0，则加入新队列 
                        if (inDegree.get(dependentTask)  == 0) { 
                            queue.add(dependentTask);  
                        } 
                    } 
                } 
            } 
        } 
 
        // 检查是否所有任务都被执行 
        if (result.size()  != inDegree.size())  { 
            // 存在循环依赖，无法完成排序，输出为空 
            System.out.println("");  
            return; 
        } 
 
        // 输出结果，任务之间用单个空格分隔 
        for (int i = 0; i < result.size();  i++) { 
            if (i != 0) System.out.print(" "); 
            System.out.print(result.get(i));  
        } 
        System.out.println();  
    } 
} 

题目内容

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如 $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