题目描述:
有若干个连续编号的服务(编号从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
# -*- 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]))