DFS 树上搜索 T2 todo 病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。
现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。
在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。
输入格式：
输入在第一行中给出一个正整数 ，即病毒种类的总数。于是我们将所有病毒从 到 进行编号。
随后 N$ 行，每行按以下格式描述一种病毒的变异情况：
k 变异株1 …… 变异株k
其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 行对应编号为 的病毒（）。题目保证病毒源头有且仅有一个。
输出格式：
首先输出从源头开始最长变异链的长度。
在第二行中输出从源头开始最长的一条变异链，编号间以 个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。
注：我们称序列 比序列 “小”，如果存在 满足 对所有 成立，且 。
输入样例：
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1输出样例：
4
0 4 9 1思路
求树上从根开始的最长路径并输出, 要求是字典序最小的方案。
刚开始想的是边读边记录每个点的深度, 找到最大深度之后用DFS按序号从小到大搜索子树, 第一个等于最大深度的点就是答案。
不过可能是因为没看到根节点不一定为0导致WA, 后来改了一下思路, 用逐步更新的方式直接进行DFS, 若当前的长度大于之前的答案长度, 就更新长度并覆盖原来的答案序列。
依然是用 array 来代替指针数组, 直接一个=号处理掉更新序列。存图的话直接用邻接表vector, 只需要遍历的话用不着idx指针邻接表存图。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <array>
using namespace std;
const int N = 1e4 + 10;
int n;
int d[N], root;
vector<int> g[N];
array<int, N> path, ans;
int max_cnt;
void dfs(int u, int cnt)
{
if(cnt > max_cnt)
{
path[cnt] = u;
ans = path;
max_cnt = cnt;
}
for(auto i : g[u])
{
path[cnt] = u;
dfs(i, cnt + 1);
}
}
int main()
{
cin >>n;
for(int i = 0; i < n; i++)
{
int m;
cin >> m;
for(int j = 0; j < m; j++)
{
int t;
cin >>t;
d[t]++;
g[i].push_back(t);
}
sort(g[i].begin(), g[i].end());
}
for(int i = 0; i < n;i ++) if(!d[i]) root = i;
dfs(root,0);
cout << max_cnt+1 << endl;
cout << ans[0];
for(int i = 1; i <= max_cnt; i++)
cout << " " << ans[i];
return 0;
}