## L2-038 病毒溯源

题目链接：https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1386335159927652361&page=1

本题还是有点难度的，需要用到回溯。同时题目还给了一些条件需要注意：如果最长链不唯一，则输出最小序列。注意要对数组排序

接下来看具体的解题代码，代码中有具体的细节解释：
```cpp
#include<bits/stdc++.h>
using namespace std;
//注意这道题还需要找到根节点，因为题目说是找最小序列，我们可以先按字典序排序，这样后面再找序列的时候就不会这么麻烦了
int max_length=0;
vector<int> res;
void dfs(vector<vector<int>> &graph,int node,vector<int>& track){
    if(track.size()>max_length){
        max_length=track.size();
        res=track;//这里赋值给res，避免丢失
    }
    for(auto a:graph[node]){
        track.push_back(a);
        dfs(graph,a,track);
        track.pop_back();
    }
}
int main(){
    int N; cin>>N;
    vector<vector<int>> graph(N);
    int num;
    //这里还需要创建一个入度数组来寻找根节点，根节点入度为0；
    vector<int> in_degree(N,0);
    for(int i=0;i<N;i++){
        cin>>num;
        for(int j=0;j<num;j++){
            int x; cin>>x;
            graph[i].push_back(x);
            in_degree[x]++;
        }
        //这里提前按照字典序排序，就可以找出最小序列
        sort(graph[i].begin(),graph[i].end());
    }
    int root;
    for(int i=0;i<N;i++){
        if(in_degree[i]==0){
            root=i;
            break;
        }
    }
    vector<int> track;//本题需要用到回溯，这里在函数中加入一个数组变量来存储
    track.push_back(root);
    dfs(graph,root,track);
    cout<<max_length<<endl;
    for(int i=0;i<res.size();i++){
        if(i>0){
            cout<<" ";
        }
        cout<<res[i];
    }
    return 0;
}