【BFS】2023A-快速开租建站

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3752

题目描述

当前 IT 部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套 IT 服务。每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为 1。部署任务项之间可能存在依赖，假如任务 2 依赖任务 1，那么等任务 1 部署完，任务 2 才能部署。任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。

输入描述

第一行是任务数 taskNum，第二行是任务的依赖关系数 relationsNum

接下来 relationsNum 行，每行包含两个 id，描述一个依赖关系，格式为：IDi IDj，表示部署任务 i 部署完成了，部署任务 j 才能部署，IDi 和 IDj 值的范围为：[0, taskNum)

注：输入保证部署任务之间的依赖不会存在环。

输出描述

一个整数，表示一个站点的最短开站时间。

备注

1 < taskNum <= 100
1 <= relationsNum <= 5000

示例一

输入

输出

说明

有 5 个部署任务项，3 个依赖关系，如下图所示。我们可以先同时部署任务项 0，任务项 1，任务项 2。然后再同时部署任务项 3 和任务项 4。最短开站时间为 2。

解题思路

注意，本题和LC1136. 并行课程几乎完全一致。唯一的区别在于，本题无需考虑存在环的情况，即一定可以完成拓扑排序，更加简单。

代码

Python

# 题目：2023Q1-快速开租建站
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：多源BFS/拓扑排序
# 代码看不懂的地方，请直接在群上提问

from collections import deque

# 输入节点数
n = int(input())
# 输入依赖关系数目
m = int(input())

# 初始化邻接表，长度为n
neighbor_table = [list() for _ in range(n)]
# 初始化入度数组，长度为n
inDegreeList = [0] * n

# 构建邻接表和入度数组
for _ in range(m):
    x, y = map(int, input().split())
    # y依赖于x，因此延长节点x的邻接表
    neighbor_table[x].append(y)
    # y的入度+1
    inDegreeList[y] += 1

# 初始化队列，用于维护BFS过程，初始化的节点为入度为0的哪些节点
q = deque( [i for i in range(n) if inDegreeList[i] == 0] )
# 搜索的层数
level = 0

# 进行BFS搜索
while len(q) > 0:
    # 获得队列的长度，为该层BFS搜索出队的节点数
    qSize = len(q)
    # 搜索层数+1
    level += 1
    # 初始qSize次
    for _ in range(qSize):
        # 当前节点
        cur = q.popleft()
        # 遍历当前节点的所有下一个点
        for nxt in neighbor_table[cur]:
            # 对于nxt，入度-1
            inDegreeList[nxt] -= 1
            # 如果nxt的入度降为0了，可以加入队列中，进行后续的BFS
            if inDegreeList[nxt] == 0:
                q.append(nxt)

print(level)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        List<List<Integer>> neighborTable = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            neighborTable.add(new ArrayList<>());
        }

        int[] inDegreeList = new int[n];

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            neighborTable.get(x).add(y);
            inDegreeList[y]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegreeList[i] == 0) {
                q.add(i);
            }
        }

        int level = 0;

        while (!q.isEmpty()) {
            int qSize = q.size();
            level++;
            for (int i = 0; i < qSize; i++) {
                int cur = q.poll();
                for (int nxt : neighborTable.get(cur)) {
                    inDegreeList[nxt]--;
                    if (inDegreeList[nxt] == 0) {
                        q.add(nxt);
                    }
                }
            }
        }

        System.out.println(level);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> neighborTable(n);
    vector<int> inDegreeList(n, 0);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        neighborTable[x].push_back(y);
        inDegreeList[y]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegreeList[i] == 0) {
            q.push(i);
        }
    }

    int level = 0;
    while (!q.empty()) {
        int qSize = q.size();
        level++;
        for (int i = 0; i < qSize; i++) {
            int cur = q.front();
            q.pop();
            for (int nxt : neighborTable[cur]) {
                inDegreeList[nxt]--;
                if (inDegreeList[nxt] == 0) {
                    q.push(nxt);
                }
            }
        }
    }

    cout << level << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。遍历所有节点

空间复杂度：O(N)。队列、邻接表、入度列表所需空间。