题目描述

当前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

输出描述

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

用例1

输入

5
5
0 4
1 2
1 3
2 3
2 4

输出

3

说明

有5个部署任务项，5个依赖关系,我们可以先同时部署任务项0和任务项1，然后部署任务项2，最后同时部署任务型3和任务型4.最短开战时间为3。

用例2

输入

5
3
0 3
0 4
1 3

输出

2

参考题库

华为OD机试2025最新题库

实现思路

• 本质是查最深依赖链长度。比较适合使用DFS来解决。其中可以使用缓存记录已经访问过的元素。减少重复递归计算。

C++

#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm>
#include<list>
#include<queue>
#include<map>
#include<set>
#include<climits>
using namespace std;

// DFS求最长深度
int DFS(map<int, vector<int>>& relationMp, int current, vector<int>& visited) {
    // 已经访问过了，利用缓存
    if (visited[current] != INT_MAX) {
        return visited[current];
    }
    
    int res = 0;
    vector<int> relys = relationMp[current];
    // 递归找到最长依赖链
    for (int i = 0; i < relys.size(); i++) {
        int time = DFS(relationMp, relys[i], visited);
        visited[relys[i]] = time;
        res = max(time, res);
    }
    visited[current] = res + 1;
    return  res + 1;
}


int main() {
    int taskNum;
    int relationNum;
    cin >> taskNum;
    cin >> relationNum;
    // 构建依赖关系
    map<int, vector<int>> relationMp;
    for (int i = 0; i < relationNum; i++) {
        int a, b;
        cin >> a >> b;
        relationMp[b].push_back(a);
    }
    int res = 1;
    // 定义缓存 防止重复递归
    vector<int> visited(taskNum, INT_MAX);
    for (int i = 0; i < taskNum; i++) {
        int time = DFS(relationMp, i, visited);
        res = max(time, res);
    }
    cout << res;
    return 0;

}