题目描述
当前IT部门支撑了子公司颗粒化业务，该部门需要实现为子公司快速开租建站的能力，建站是指在一个全新的环境部署一套IT服务。
- 每个站点开站会由一系列部署任务项构成，每个任务项部署完成时间都是固定和相等的，设为
1。 - 部署任务项之间可能存在依赖，假如任务
2依赖任务1，那么等任务1部署完，任务2才能部署。 - 任务有多个依赖任务则需要等所有依赖任务都部署完该任务才能部署。
- 没有依赖的任务可以并行部署，优秀的员工们会做到完全并行无等待的部署。
给定一个站点部署任务项和它们之间的依赖关系，请给出一个站点的最短开站时间。
输入描述
第一行是任务数
第二行是任务的依赖关系数
接下来的
行，每行包含两个
，描述一个依赖关系，格式为
- 表示任务部署完成了，任务才能够部署
- 的取值范围为：
注：输入保证部署任务之间的依赖不会存在环。
输出描述
- 一个整数，表示一个站点的最短开站时间
备注
用例
用例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- 说明
- 存在 5 个部署任务项，3个依赖关系
- 可以同时部署 任务 0 、1 、2
- 然后同时部署任务 3、4
- 最短开站时间为 2
题目解析
- 直观地，要想找到最短的开站时间，那么每一次应该尽可能多得去处理任务。（这里并行处理的数量没有限制）
- 所以，每一次要找到可以处理的所有任务进行处理就好了，那么问题在于如何每一次找到可以处理的所有任务
- 根据依赖关系图的话，那么不在依赖关系中的任务，很显然可以忽略，因为这些任务可以一次性处理。
- 那么根据图，很显然，根节点的任务可以最先处理。那么其实可以只考虑依赖关系，因为不在依赖关系内的任务仅仅需要一次就可以处理完
- 这块如何用代码处理——犯难了，图论部分掌握的实在不怎么滴
- 参考大佬代码之后整理思路
- 首先最先处理的任务肯定是不依赖其它任务的任务，即在图中的表现是跟节点。那么首先就要从这些跟节点开始处理
- 那么好，肯定要记录这些跟节点，为了统一，可以把不在依赖关系外的节点也认为是根节点，这样方便处理
- 根据这个处理方法，第一次处理完所有的跟节点任务，那么移除这些跟节点
- 然后，剩下的节点中肯定会有一组新的根节点
- 这样依次处理，最后得到——最短开站时间
- 那么然后如何处理数据？
- 首先，节点之间的关系可以用
Map<Integer, new ArrayList<>()>来存储 - 然后呢需要记录每一个节点有多少个前置节点，因为一共有
taskNum个任务，所以可以用一个数组来记录 - 再然后，记录第一次需要处理的根节点。从每一个根节点出发处理完路径上的所有任务。那么每一个根节点对应有一个处理任务所消耗的时间，记录最大的时间即为最终的最短建站时间
- 所以，这里可以用数据结构
LinkedList<Integer[]>来处理
代码展示
package com.hw;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128577041">快速开租建站</a>
* <p>
* create time : 2023/7/2 19:08
*/
public class SiteBoost {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int taskNum = in.nextInt();
int relationsNum = in.nextInt();
int[][] relations = new int[relationsNum][2];
for(int i = 0;i < relationsNum;i++) {
relations[i][0] = in.nextInt();
relations[i][1] = in.nextInt();
}
siteBoost(relations, taskNum);
}
private static void siteBoost(int[][] relations, int taskNum) {
// 那么首先需要的是，建图，用图来表示依赖关系
HashMap<Integer, ArrayList<Integer>> chart = new HashMap<>();
int[] degree = new int[taskNum];
for (int[] relation : relations) {
// 前置任务
int a = relation[0];
// 后置任务
int b = relation[1];
chart.putIfAbsent(a, new ArrayList<>());
chart.get(a).add(b);
// 记录 任务b 拥有多少个前置任务
degree[b]++;
}
LinkedList<Integer[]> queue = new LinkedList<>();
int cnt = 1;
for(int i = 0;i < taskNum;i++) {
if(degree[i] == 0) {
queue.add(new Integer[]{i, cnt});
}
}
while(queue.size() > 0) {
Integer[] reF = queue.removeFirst();
int task = reF[0];
int time = reF[1];
if(chart.containsKey(task) && chart.get(task).size() > 0) {
// 遍历当前节点的后置节点
for (Integer nxt : chart.get(task)) {
degree[nxt]--;
if(degree[nxt] == 0) {
cnt = time + 1;
queue.add(new Integer[]{nxt, cnt});
}
}
}
}
System.out.println(cnt);
}
}