二、 【编程|30分】致命分裂 题目描述
有初代病毒T,不致命,T经过一段时间后,会分裂出多个子代病毒(数量不定)。又经过一段后,每一个子代病毒又可能各自分裂出自己的子代。原始病毒不致命,但病毒在分裂过程产生的子代病毒会突发产生致命性。每个子代病毒,可以通过基因追溯到他的上代病毒。在已定位到多个产生致命性的病毒、知道其编号的情况下,需要找到这多个致命病毒的最近共同祖先病毒(唯一且非致命)。
注:
1.假设初始病毒T,不致命,编号为0
2.一段时间和多次子代分裂后,共产生N-1个病毒,编号为1到N-1
3.致命病毒随机在1到N-1的各子代病毒中产生,至少1个
4.致命病毒的子代病毒可能致命也可能不致命
输入描述:
第1行有2个数字,第一个代表共有N个病毒,第二个代表共有R条分裂关系
第2行第一个数字代表有M个致命病毒,后面的M个数字为致命病毒的编号
第3行起后面R行,每一行是一个分裂关系,第一个数字代表亲代病毒的编号,第二个数字代表子代病毒的数量c,后面为c个子代病毒的编号
输出描述:
所有致命病毒的最近共同祖先病毒(唯一且非致命)编号
示例1 输入输出示例仅供调试,后台判题数据一般不包含示例
输入
4 2 2 2 3 0 2 1 2 1 1 3 |
0 |
第一行:总共4个病毒,2组关系 第二行:2个致命病毒,分别为2号和3号 第三行: 0号病毒有2个子病毒,分别为1号和2号 第四行:1号病毒有1个子病毒,为3号 |
推荐阅读
- 笔试题|字节跳动2021春招研发第二场笔试编程题(三)
- 笔试-算法|【算法】2021-3-7字节跳动2022春招笔试第一场第二题 (庆祝61)
- 算法和数据结构|字节跳动 2021 春招面试高频题3
- 算法|字节跳动21春招第三场笔试算法题
- 算法|字节跳动2019春招研发编程题
- java|Java——字节跳动2019春招研发部分编程题(一)
- 软件测试|软件测试3个月学习,终于找到工作了,面试总结分享给大家
- 软件测试|Postman 是个好用的工具,不试一下()
- Android|Android 知识点 030 —— Handler,Thread,HandlerThread