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\)个关注的人里不会包含自己