while q:
    nodes_new = list()
    qSize = len(q)
    for _ in range(qSize):
        cur_node = q.popleft()
        for nxt_node in neighbor_dic[cur_node]:
            indegree_dic[nxt_node] -= 1
            if indegree_dic[nxt_node] == 0:
                nodes_new.append(nxt_node)
                q.append(nxt_node)
    nodes_new.sort()
    ans += nodes_new

代码

Python

# 题目：【BFS】2024E-启动多任务排序
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：BFS/拓扑排序
# 代码看不懂的地方，请直接在群上提问


from collections import deque, defaultdict

# 对输入进行分割，得到若干个字符串，每一个字符串包含依赖关系
lst = input().split()
# 构建邻接表
neighbor_dic = defaultdict(list)

# 构建入度哈希表（因为节点名字是字符串而不是数字，因此用哈希表而不是数组）
indegree_dic = defaultdict(int)

# 遍历lst中的每一对依赖关系
for pairs in lst:
    # 根据"->"进行分割，得到节点a和b
    # "a->b"表示节点a依赖于节点b
    # 必须执行节点b之后，才能执行节点a
    a, b = pairs.split("->")
    # a为b的邻居，延长b的邻接节点
    neighbor_dic[b].append(a)
    # 节点a的入度增加
    indegree_dic[a] += 1

# 初始化答案数组，其中入度为0的节点为初始节点，同时根据字典序进行排序
ans = sorted(k for k in neighbor_dic.keys() if indegree_dic[k] == 0)
# 初始化队列，其中队中元素为ans中的元素
q = deque(ans)

# BFS
while q:
    # 初始化一个列表，储存新出现的入度为0的节点
    # 新出现的这些节点，需要在for循环结束后立即执行，加入到ans中
    nodes_new = list()
    # 获得当前层的节点数
    qSize = len(q)
    # 循环qSize次，弹出队列中所有节点
    for _ in range(qSize):
        # 弹出当前队头节点cur_node
        cur_node = q.popleft()
        # 考虑cur_node的所有近邻节点nxt_node
        for nxt_node in neighbor_dic[cur_node]:
            # 近邻nxt_node的入度-1
            indegree_dic[nxt_node] -= 1
            # 如果该近邻节点的入度降为0
            if indegree_dic[nxt_node] == 0:
                # 将其加入nodes_new数组中
                nodes_new.append(nxt_node)
                # 将其加入q中
                q.append(nxt_node)
    # 对nodes_new根据字典序进行排序，然后加在ans后面
    # 表示需要立即执行nodes_new中的节点
    nodes_new.sort()
    ans += nodes_new

print(*ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] lst = input.split(" ");
        Map<String, List<String>> neighborDic = new HashMap<>();
        Map<String, Integer> indegreeDic = new HashMap<>();

        for (String pairs : lst) {
            int pos = pairs.indexOf("->");
            String a = pairs.substring(0, pos);
            String b = pairs.substring(pos + 2);

            neighborDic.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            indegreeDic.put(a, indegreeDic.getOrDefault(a, 0) + 1);
        }

        List<String> ans = new ArrayList<>();

        for (String node : neighborDic.keySet()) {
            if (!indegreeDic.containsKey(node)) {
                ans.add(node);
            }
        }

        Collections.sort(ans);
        Queue<String> q = new LinkedList<>(ans);

        while (!q.isEmpty()) {
            List<String> nodesNew = new ArrayList<>();
            int qSize = q.size();

            for (int i = 0; i < qSize; i++) {
                String curNode = q.poll();

                if (neighborDic.containsKey(curNode)) {
                    for (String nxtNode : neighborDic.get(curNode)) {
                        indegreeDic.put(nxtNode, indegreeDic.get(nxtNode) - 1);
                        if (indegreeDic.get(nxtNode) == 0) {
                            nodesNew.add(nxtNode);
                            q.add(nxtNode);
                        }
                    }
                }
            }

            Collections.sort(nodesNew);
            ans.addAll(nodesNew);
        }

        for (String node : ans) {
            System.out.print(node + " ");
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    string input;
    getline(cin, input);
    vector<string> lst;
    string temp;
    for (char i : input) {
        if (i == ' ') {
            lst.push_back(temp);
            temp = "";
        } else {
            temp += i;
        }
    }
    lst.push_back(temp);

    unordered_map<string, vector<string>> neighborDic;
    unordered_map<string, int> indegreeDic;

    for (string pairs : lst) {
        string delimiter = "->";
        size_t pos = pairs.find(delimiter);
        string a = pairs.substr(0, pos);
        string b = pairs.substr(pos + delimiter.length());

        neighborDic[b].push_back(a);
        indegreeDic[a]++;
    }

    vector<string> ans;

    for (auto node : neighborDic) {
        if (indegreeDic.find(node.first) == indegreeDic.end()) {
            ans.push_back(node.first);
        }
    }
    
    sort(ans.begin(), ans.end());
    queue<string> q;
    for (string node : ans) {
        q.push(node);
    }

    while (!q.empty()) {
        vector<string> nodesNew;
        int qSize = q.size();

        for (int i = 0; i < qSize; i++) {
            string curNode = q.front();
            q.pop();

            if (neighborDic.find(curNode) != neighborDic.end()) {
                for (string nxtNode : neighborDic[curNode]) {
                    indegreeDic[nxtNode]--;
                    if (indegreeDic[nxtNode] == 0) {
                        nodesNew.push_back(nxtNode);
                        q.push(nxtNode);
                    }
                }
            }
        }
        sort(nodesNew.begin(), nodesNew.end());
        ans.insert(ans.end(), nodesNew.begin(), nodesNew.end());
    }

    for (string node : ans) {
        cout << node << " ";
    }

    return 0;
}

Node JavaScript

const readline = require("readline");

// 主函数
function main(input) {
    // 将输入的字符串分割成依赖对
    const lst = input.split(" ");

    // 构建邻接表和入度表
    const neighborDic = new Map(); // 邻接表
    const indegreeDic = new Map(); // 入度表

    // 遍历依赖对，建立图的结构
    lst.forEach(pair => {
        const pos = pair.indexOf("->");
        const a = pair.substring(0, pos); // 起点
        const b = pair.substring(pos + 2); // 终点

        // 构建邻接表
        if (!neighborDic.has(b)) {
            neighborDic.set(b, []);
        }
        neighborDic.get(b).push(a);

        // 构建入度表
        indegreeDic.set(a, (indegreeDic.get(a) || 0) + 1);
    });

    // 初始化答案数组
    const ans = [];
    // 找到所有入度为 0 的节点并排序
    for (const node of neighborDic.keys()) {
        if (!indegreeDic.has(node)) {
            ans.push(node);
        }
    }
    ans.sort(); // 按字典序排序

    // BFS 队列初始化
    const queue = [...ans];

    // BFS 开始
    while (queue.length > 0) {
        const nodesNew = []; // 当前层新出现的入度为 0 的节点
        const qSize = queue.length;

        for (let i = 0; i < qSize; i++) {
            const curNode = queue.shift(); // 弹出队头节点

            // 遍历当前节点的邻接节点
            if (neighborDic.has(curNode)) {
                for (const nxtNode of neighborDic.get(curNode)) {
                    // 更新入度
                    indegreeDic.set(nxtNode, indegreeDic.get(nxtNode) - 1);
                    // 入度为 0 的节点加入队列
                    if (indegreeDic.get(nxtNode) === 0) {
                        nodesNew.push(nxtNode);
                        queue.push(nxtNode);
                    }
                }
            }
        }

        // 当前层的节点按字典序排序并加入答案
        nodesNew.sort();
        ans.push(...nodesNew);
    }

    // 输出结果
    console.log(ans.join(" "));
}

// 读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.question("", (line) => {
    main(line);
    rl.close();
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strings"
)

// 主函数
func main() {
        // 读取输入
        reader := bufio.NewReader(os.Stdin)
        input, _ := reader.ReadString('\n')
        input = strings.TrimSpace(input)
        lst := strings.Fields(input)

        // 构建邻接表和入度表
        neighborDic := make(map[string][]string) // 邻接表
        indegreeDic := make(map[string]int)      // 入度表

        // 遍历依赖对，建立图的结构
        for _, pair := range lst {
                pos := strings.Index(pair, "->")
                a := pair[:pos]   // 起点
                b := pair[pos+2:] // 终点

                // 构建邻接表
                neighborDic[b] = append(neighborDic[b], a)

                // 构建入度表
                indegreeDic[a]++
        }

        // 初始化答案数组
        var ans []string

        // 找到所有入度为 0 的节点
        for node := range neighborDic {
                if _, exists := indegreeDic[node]; !exists {
                        ans = append(ans, node)
                }
        }
        sort.Strings(ans) // 按字典序排序

        // BFS 队列初始化
        queue := append([]string{}, ans...)

        // BFS 开始
        for len(queue) > 0 {
                nodesNew := []string{} // 当前层新出现的入度为 0 的节点
                qSize := len(queue)

                for i := 0; i < qSize; i++ {
                        curNode := queue[0]
                        queue = queue[1:] // 出队

                        // 遍历当前节点的邻接节点
                        if neighbors, exists := neighborDic[curNode]; exists {
                                for _, nxtNode := range neighbors {
                                        // 更新入度
                                        indegreeDic[nxtNode]--
                                        // 入度为 0 的节点加入队列
                                        if indegreeDic[nxtNode] == 0 {
                                                nodesNew = append(nodesNew, nxtNode)
                                                queue = append(queue, nxtNode)
                                        }
                                }
                        }
                }

                // 当前层的节点按字典序排序并加入答案
                sort.Strings(nodesNew)
                ans = append(ans, nodesNew...)
        }

        // 输出结果
        fmt.Println(strings.Join(ans, " "))
}

时空复杂度

时间复杂度：O(N)。

空间复杂度：O(N)。