有依赖关系的服务器启动
有若干个服务器(编号从0开始),服务器间有依赖,启动一个指定服务器,判定一下能不能启动成功。比如服务器1依赖服务器4,5,那么要想启动服务器1,就要先启动服务器4与服务器5。
第一行输入服务器N,表示服务器的个数。第二行输入M,表示要启动的指定服务器。接下来的n行,是从标号0~n-1服务器的依赖表,每一个的第一个数字表示依赖的数量,后面表示所依赖的服务器编号。
对于输出,如果服务器启动依赖之间存在环,则输出“-1”,如果指定服务器启动没有前置依赖输出“null”,如果指定服务器启动存在合法的依赖服务器的启动顺序,则按照从小到大的顺序,输出所依赖服务器的标号,不包括指定服务器本身。
输入
4
2
0
1,0
1,1
2,0,1
输出:
0,1
输入
5
0
2,1,2
0
2,1,3
1,4
1,2
输出:
-1
解析:指定服务器的依赖表,要注意判断一下有没有存在环,当然这个环不是简单的编号重复,是存在着方向的。如下图:
如果指定启动的是0号服务器,那么首先我们要启动它的直接依赖[1, 2],对1号服务器没有依赖了,就结束了,对于2号服务器,它还有前置依赖[3],对于3号服务器,它还有前置依赖[4],对于4号服务器的启动,就存在了环。但对于下图,启动指定服务器0,则是合法的,依赖服务器的启动顺序为[1,2,3,4]
1 n = int(input()) 2 m = int(input()) 3 arr = [] 4 open_order = [] 5 stack = [] #记录打开的依赖 6 for _ in range(n): 7 arr.append(list(map(int, input().split(',')))) 8 9 def find(i): 10 if open_order[0] == "-1": return 11 stack.append(i) 12 if arr[i][0]>0: #依赖服务器标号长度 13 for j in arr[i][1:]: 14 if j not in stack: 15 if j not in open_order: 16 open_order.append(j) 17 find(j) 18 else: 19 open_order[0] = -1 20 break 21 stack.pop() 22 open_order.append(m) 23 find(m) 24 if open_order[0] == -1: 25 print("-1") 26 else: 27 open_order.remove(m) 28 if len(open_order) == 0: 29 print("null") 30 else: 31 open_order.sort() 32 print(' '.join(map(str, open_order))) 33 #null 34 # order_list