有依赖关系的服务器启动


有若干个服务器(编号从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