Problem 5E. 死锁

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5E. 死锁

时间限制:1000ms

空间限制:256MB

题目背景

有一天,小泽正在宿舍里快乐的coding,他准备等左手边的小宇睡觉他就去睡觉。可是等了半天都1点了小宇都没睡,于是他问小宇:“你为什么不睡觉啊?”小宇却反问他:“你今天怎么这么能熬?我还在等你睡觉呢。”于是这两人就形成了一个死锁。现实生活中,像几个软件的线程互相等待对方导致死机,或者环岛上等待前方挪动的汽车都会形成这种死锁现象。

题目描述

于是,小泽就给这种宿舍不睡觉现象建立了一个模型。现在宿舍里有n个人,其中第i个人(\(1 \le i \le n\))关注着 \(a_i\) 个不同的其他人(不包括自己)。只要其中有 \(b_i\)个人睡觉了,这个人就会立马睡觉。特别的,当 \(b_i=0\) 时,这个人会立刻睡觉。现在,小泽想问宿舍里还剩那些人不会立刻睡觉,形成了一个死锁?

输入格式

第一行一个正整数 \(n\),表示宿舍的总人数。
接下来 \(n\) 行,第i行先是两个整数 \(a_i\) 和 \(b_i\),接着 \(a_i\)个数字表示第i个人关注的人。

输出格式

输出一系列整数,表示没立刻睡觉的人。如果都睡了就输出-1。

样例输入1

6
0 0
0 0
1 1 4
1 1 3
2 2 1 2
5 4 1 2 3 4 5

样例输出1

3 4 6

样例1解释

1和2直接睡了,3和4互相关注,于是都没睡。5关注1和2两人,两人都睡了,于是5也睡了。6关注1到5,其中3和4都没没睡,于是其中睡觉的人小于4人,没有睡觉。

数据范围及约定

对于50%的数据,\(n \le 100\), \(a_i\) 的和 \( \le 500\), \(b_i \le a_i\)。

对于100%的数据,\(n \le 2 * 10^4\), \(a_i\)的和\(\le 10^5\), \(b_i \le a_i\)。

保证 \(a_i=0\) 当且仅当 \(b_i=0\) 时成立,且 \(a_i\)个关注的人里不会包含自己

2024春 悬赏令第五周

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-05-13 00:00
结束于
2024-05-19 00:00
持续时间
144.0 小时
主持人
参赛人数
52