2021天梯赛L2-038 病毒溯源

病毒溯源
题目描述：
病毒总类总数n，编号0~n-1，n行数据，第i行对应编号i-1病毒的变异毒株种类个数及编号，要求输入最长变异序列长度以及变异链，长度相等时输出最小序列，注意题目保证病毒源头有且仅有一个。

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=1000010;
vector<vector<int> >g; 
int n,cnt;
bool vis[N];
vector<int>ans,temp;
void dfs(int u,int sum){
    if(sum>cnt){
        cnt=sum;
        ans=temp;
    }
    else if(sum==cnt&&temp<ans){
        ans=temp;
    }
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        temp.push_back(v);
        dfs(v,sum+1);//回溯 
        temp.pop_back();
    }
}
int main(){
    int n;
    cin>>n;
    g.resize(n+1);//申请空间 
    for(int i=0;i<n;++i){
        int k;
        cin>>k;
        while(k--){
            int x;
            cin>>x;
            vis[x]=true;
            g[i].push_back(x);
        }
    }
    int root=0;
    while(vis[root])root++;//由于只有一个病毒源头所以可以这样找到根病毒 
    dfs(root,1);//从根开始dfs找到最长的最小序列
    cout<<cnt<<endl;
    cout<<root;
    for(int i=0;i<ans.size();++i)
    cout<<" "<<ans[i]; 
    return 0;
}