【华为OD机试2023】快速开租建站Python

题目描述：

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

说明：

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

解题思路：

所谓的依赖关系，就是必须依赖的任务完成才能开始本任务，那么找到最短开站时间，其实就是找出一条最长的依赖链，（因为所有任务的部署时间都是1，所以）这条链的长度就是最短时间。

用回溯法，遍历所有任务，从该任务一直往回倒，直到倒无可倒，就是遍历完成一条依赖链，然后取所有依赖链的最大值即可

taskNum=int(input())
relaNum=int(input())
relas=[list(map(int,input().split())) for i in range(relaNum)]
relas_dic={}
for rela in relas:
    if relas_dic.get(rela[1])==None:
        relas_dic[rela[1]]=[rela[0]]
    else:
        relas_dic[rela[1]].append(rela[0])
res=[]
count=0
def backtracking(res,start,count):
    if relas_dic.get(start)==None:
        count+=1
        res.append(count)
        return
    for i in relas_dic[start]:
        count+=1
        backtracking(res,i,count)
        count-=1
for j in range(taskNum):
    backtracking(res,j,count)
print(max(res))