题目描述
自己看题目
样例
自己看题目
算法1
(递归) $O(n)$
时间复杂度
参考文献
C++ 代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
//int f[10010];
vector<int>a[10010];
bool sc[10010];
int ceng = 0;
//int len = 0;
int bet[10010];//better:最好的 bet[x]:记录的是根节点为x 子节点中最好的选择
int msn(int x) {
int len = 0;
for (int i = 0; i < a[x].size(); i++) {
int k = msn(a[x][i]);
if (k > len) len = k, bet[x]=a[x][i];
else if (k == len&&a[x][i] < bet[x])bet[x] = a[x][i];//在递归过程中就会将bet填充完全
}
return len + 1;
}
int main() {
memset(bet, -1, sizeof bet);
int ceng = 0;
int n;
scanf("%d", &n);
//找到第一层
for (int i = 0; i < n; i++) {
int k;
scanf("%d", &k);
while (k--) {
int x;
scanf("%d", &x);
a[i].push_back(x);
sc[x] = 1;
}
}
int root;
for (int i = 0; i < n; i++)
{
if (!sc[i]) { root = i; break; }
}
int len = msn(root);
printf("%d\n", len);
printf("%d ", root);//先打印根节点
while (bet[root] != -1) {
printf("%d ", bet[root]);
root = bet[root];
}
return 0;
}
自己看题目