一个病毒不具有攻击性，但是可能分裂出具有攻击性的病毒
现给母细胞编号为0，其分裂的后代依次编号
几代以后，出现几个变异体
需要找出这几个变异体最近的共同祖先（祖先不具有攻击性）
输入：
正整数N代表分裂过程中具有编号的病毒数量
正整数m代表分裂次数
m行，每行第一个数字代表分裂前的祖先编号，第二个数字代表分类数量，后面若干个数字代表分裂后的后代编号
正整数k，后接k个编号代表有攻击性的病毒
输出：
一个数字，具有攻击性的病毒的公共祖先
原案例我不记得了，这个是我临时构造的
案例input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 12 9
output:
1
解法：
构造一种数据结构
其中包含两个数字，第一个是自身编号，第二个是上级祖先编号
用哈希表构建一个关系表，里面存放映射关系
用一个数组virus存放具有攻击性的病毒的编号
第一轮对数组virus寻找依次祖先，自身赋值为祖先的编号（如果是0直接返回），找出编号最小的作为共同祖先，假设变量common表示
对virus数组依次遍历，对小于common的元素继续寻找祖先，如果找到比common更小的元素，则将common赋予该值
直到所有的元素都是common，此时的common就是我们要的答案
补充：
建议先用树结构把整个关系表画出来
时间复杂度：O(N)
空间复杂度：O(N)
本题采用了哈希表unorded_map的数据结构，如果用一个vector<pair<int, int>>来记录关系表，会增加时间复杂度
更多案例：
案例2：
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 9 11
output:
0
案例3：
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
2 7 12
output:
4
案例4：
input:
15
8
0 3 1 2 3
1 2 4 5
2 1 6
4 2 7 8
5 1 9
6 2 10 11
8 1 12
9 2 13 14
3 7 13 10
output:
0
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
void FindCommonAncestor(void) {
int n, m;
while (cin >> n >> m) {
unordered_map<int, int> relationship;
for (int i = 0; i < m; i++) {
int parent, num;
cin >> parent >> num;
for (int j = 0; j < num; j++) {
int child;
cin >> child;
relationship[child] = parent;
}
}
int virusNum;
cin >> virusNum;
vector<int> virus(virusNum);
for (auto &v : virus) {
cin >> v;
//第一次寻找祖先
v = relationship[v];
}
int common = *min_element(virus.begin(), virus.end());
while (count(virus.begin(), virus.end(), common) != virus.size()) {
for (auto& v : virus) {
if (v > common)
v = relationship[v];
}
common = *min_element(virus.begin(), virus.end());
}
cout << common << endl;
}
}
int main() {
//笔试第二题
FindCommonAncestor();
return 0;
}
欢迎批评和指正
全部评论
(1) 回帖