笔试题|字节跳动2021春招研发第二场笔试编程题(二)

二、 【编程|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春招研发第二场笔试编程题(二)】

    推荐阅读