【华为机试】2023年真题B卷(python)-服务启动

发布时间:2023年12月26日

一、题目

题目描述:
有若干个连续编号的服务(编号从0开始),服务间有依赖关系,启动一个指定服务,请判断该服务是否可以成功启动,并输出以来的前置服务编号(依赖关系是可以传递的,比如服务2依赖服务1,服务1依赖于服务0,那么服务2依赖于服务1和服务0)。

二、输入输出

输入描述:
第一行输入为N,N为服务的总个数(1 <= N <= 5000)?
第二行输入为M,M为指定启动服务的编号(0 <= M < 5000) 接下来的N行,是从编号0服务~编号N-1服务的服务依赖表,每一行第一个数字是该服务依赖的服务个数T(0 <= T < 5000),后面T个数字分别是对应的依赖服务编号
输出描述:

为了避免不同算法的服务加载顺序不同,请从服务编号从小到大以此输出所有前置服务的编号,不包括指定启动的服务编号自身。
如果没有依赖的前置服务则输出null。
如果服务无法启动(出现循环依赖,则服务无法启动)或其它异常,输出-1.

三、示例

示例1 :
输入:?
4?
2?
0?
1,0?
1,1?
2,0,1?
输出:?
0,1?
解释: 第一行,4,一共四个服务,编号0~3 第二行,2,指定启动编号为2的服务 第三行开始为服务依赖关系表 第三行,0,表示服务0,没有依赖的前置任务,依赖个数为0 第四行,1,0,表示服务1,依赖1个前置任务,编号为0 第三行,1,1,表示服务2,依赖1个前置任务,编号为1 第三行,2,1,0 表示服务3,依赖2个前置任务,编号为0和1 分析,服务启动顺序为0,1,2,可成功启动服务2,输出0,1
示例2 :
输入:?
2?
1?
1,1?
1,0?
输出:?
-1

四、解题思路?

DFS

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-服务启动.py
@Time    :   2023/12/26 18:42:54
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''
# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def find_dependency_numbers(n, m, dependencys):
    loop_flag = False
    dependency_numbers = set()

    def dfs(dependencys, i, visited):
        nonlocal loop_flag
        nonlocal m
        nonlocal dependency_numbers

        if visited[i]:
            loop_flag = True
            return

        if not loop_flag:
            if m != i:
                dependency_numbers.add(i)
            visited[i] = True
            for j in dependencys[i]:
                dfs(dependencys, j, visited)
            visited[i] = False

    dfs(dependencys, m, [False for _ in range(n)])

    if loop_flag:
        return -1
    else:
        return list(dependency_numbers)

n = int(input())
m = int(input())

dependencys = []
for i in range(n):
    num = [int(x) for x in input().split(",")]
    k = num[0]
    dependencys.append(num[1:k+1])

result = find_dependency_numbers(n, m, dependencys)
if result == -1:
    print(result)
else:
    print(",".join([str(x) for x in result]))

文章来源:https://blog.csdn.net/u014481728/article/details/135230000
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。