算法1
(暴力枚举) $O(n^2)$
自底向上法
代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1E4 + 9;
vector<int> E[N];
int ans[N];
int son[N], root = 0;///这个数组用于记录答案路径,
bool st[N];
int f[N];
int cen = 1;
int dfs(int x, int p){
f[x] = 1; //各个点是1
int len = 0;
for(int i = 0; i < E[x].size(); ++ i){
int k = E[x][i];
if(k == p) continue;
//cen ++;
int L = dfs(k, x);///自下而上,优先递归的叶子结点,
if(L > len) len = L, ans[x] = E[x][i];//更新
else if(L == len && ans[x] > E[x][i]) ans[x] = E[x][i];// 比较取最小,同一层有多个向下递归
f[x] = max(f[x], f[k] + 1);//记录最长路径--自底向上
}
//cen --;
return len + 1;//到达叶子时,return,第一个记录1.。
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
memset(ans, -1, sizeof(ans));
for(int i = 0; i < n; ++ i){
int x; cin >> x;
if(!x) continue;
while(x --){
int k; cin >> k;
st[k] = true;//谁作为儿子,谁就不是根节点,打标记
E[i].push_back(k);
}
}
while(st[root]) root ++;
//ans[0] = root;
dfs(root,-1);
cout << f[root] << '\n';
cout << root;
// while (ans[root] != -1) {
// printf("%d ", ans[root]);根的含义,三种输出方式
// root = ans[root];
// }
//for(int i = ans[root]; i != -1; root = ans[root], i = ans[root]) cout << " " << i;
for(int i = root; ans[i] != -1; i = ans[i]) cout << " " << ans[i];
return 0;
}