求题解
2023-10-15 14:08:15
发布于：陕西
3阅读
0回复
0点赞
题目描述
有 n 个房间，房间按从 0 到 n−1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是尽可能进入更多的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
输入格式
第一行一个整数 n(1≤n≤1000)，表示房间的数目。
接下来 n 行，第 i 行为房间编号为 i−1 房间的信息。每行先有一个整数 k(0≤k≤n)，表示该房间的钥匙数量。接下来 k 个整数 x(0≤x<n)，表示钥匙能打开的房间编号。
输出格式
输出能够进入的房间数量。
样例组输入#1
4
1 1
1 2
1 3
0
样例组输出#1
4
样例组输入#2
4
2 1 3
3 3 0 1
1 2
1 0
样例组输出#2
3
全部评论 1
这道题可以用拓扑排序来做，就是拓扑排序的模板题。在拓扑排序中，创建一个计数器count来记录可以被走到的房间数量，之后在队列中每弹出一个房间，就将计数器增加。最后比对count == n即可。
2023-10-16 来自 上海
0
有帮助，赞一个