/ Vijos / 题库 /

复杂的按钮

复杂的按钮

时间限制:1秒  内存限制:256M


【题目描述】

  小K在遗迹探险中遇到 \(n\) 个开关,刚开始所有按钮都处于开状态,小K的经验告诉他把所有按钮按下时会有好事发生,可是有些按纽按下时会让其他一些已经闭合的按钮弹开(本就开着当然不变)。经过研究,每个按钮都对应着一个固定的弹开集合,这个按钮按下时,弹开集合中所有的按钮都会变为开状态。现在小K想知道是否能让所有的按钮变为闭状态。如果能,打印最少步数以及方案,否则打印“no solution”。

【输入格式】

  第一行一个整数 \(n\),表示 \(n\) 个按钮,接下来 \(n\) 行,表示编号为 1 到 \(n\) 的按钮的弹开集合,格式为 \(m_i\ B_1\ B_2\ …\ B_{m_i}\),意即编号为 \(i\) 的按钮按下,会让编号为 \(B_1\ B_2\ …\ B_{m_i}\) 的按钮弹起(注:其中不会出现重复)。

【输出格式】

  如果无解,输出“no solution”。 否则,第一行输出最少步数 \(Ans\),第二行输出用空格分开的 \(Ans\) 个数,表示按顺序按下编号为这些数的按钮就可以解决。 如果有多种方案,输出字典序最小的方案数。

【输入输出样例】

 Input

6
2 2 3
0
2 4 5
0
0
0

 Output

6
1 2 3 4 5 6

【数据限制】

  对于 \(100\%\) 的数据,\(1≤n≤30000\),\(0≤ m_1 + m_2 + … + m_i≤ 1000000\)。

【来源】

  Mr.he

信息

ID
1871
难度
(无)
分类
图结构 | 拓扑排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者