C++ 代码:查找家族家谱中的最小辈分
思路:
- 首先将输入的家谱存储为一个vector<int>的数组,数组下标表示成员编号,数组值表示父/母编号。
- 创建一个vector<int>的数组level,用来存储每个成员的辈分。
- 从老祖宗开始,递归地计算每个成员的辈分,直到计算到没有父/母的成员为止。
- 统计辈分最小的成员的编号,输出最小的辈分和编号。
代码如下:
#include <iostream>
#include <vector>
using namespace std;
// 递归计算成员的辈分
int calculateLevel(vector<int>& family, vector<int>& level, int member) {
if (level[member] != 0) {
return level[member];
}
int parent = family[member];
if (parent == -1) {
level[member] = 1;
} else {
level[member] = calculateLevel(family, level, parent) + 1;
}
return level[member];
}
int main() {
int N;
cin >> N;
vector<int> family(N + 1);
for (int i = 1; i <= N; i++) {
cin >> family[i];
}
vector<int> level(N + 1, 0);
int minLevel = INT_MAX;
for (int i = 1; i <= N; i++) {
int curLevel = calculateLevel(family, level, i);
minLevel = min(minLevel, curLevel);
}
cout << minLevel << endl;
for (int i = 1; i <= N; i++) {
if (level[i] == minLevel) {
cout << i << " ";
}
}
return 0;
}
原文地址: https://www.cveoy.top/t/topic/pPAa 著作权归作者所有。请勿转载和采集!