服务启动

【华为校园招聘软件】 2022-04-06

编程题 （第2/3题）

【编程题目 | 200分】服务启动 [ 2022 考试题 ]

2、服务启动

■ 题目描述

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

解答要求

• 时间限制：C/C++1000ms，其他语言：2000ms
• 内存限制：C/C++256MB，其他语言：512MB

输入

• 第一行输入为N，N为服务的总个数（1<= N<= 5000）
• 第二行输入为M，M为指定启动服务的编号（0 <= M < 5000）
• 接下来N行，是从编号0服务 ~ 编号N-1服务的服务依赖表，每一行第一个数字是该服务依赖的服务个数T（0 <= T < 5000），后面T个数字分别是对应的依赖服务编号。

输出

• 为了避免不同算法的服务加载顺序不同，请按服务编号从小到大依次输出所有前置服务的编号，不包括指定启动的服务编号自身。
• 如果没有依赖的前置服务则输出 null。
• 如果服务无法启动（出现循环依赖，则服务无法启动，样例2为最简单的循环依赖）或其他异常，则输出 -1。

样例1

输入

4
2
0
1,0
1,1
2,0,1

输出

0,1

代码实现

C++

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

class Node {
public:
    set<int> depends;
};

STICK永久会员

打赏 收藏 海报 链接