病毒溯源

链接

题意：给定一些病毒之间的变异关系，找出其中最长的一条变异链。不考虑循环遍历。有N种病毒，每种病毒都有k个二代变异病毒。保证源头只有一个。

题解：深度优先搜索DFS，因为题目中规定源头只有一个，所以把所有的二代变异病毒都储存起来，找到唯一一种没有出现在二代变异的病毒，把他作为源点，开始深搜，否则的话会TLE。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e5+15;
const int mod = 1e9+7;
int h[N],e[N],ne[N];
int dit=0;
int ans = 0;
vector<int> res , v;
bool st[N];
int flag[N];
void add(int a,int b)
{
    e[dit] = b;
    ne[dit] = h[a];
    h[a] = dit++;
}

void dfs(int u,int dist)
{
    if(dist>ans)
    {
        res = v;
        ans = dist;
    }
    else if(dist==ans && v<res)
    {
        res = v;
    }
    for(int i = h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(st[j]==false)
        {
            st[j] = true;
            v.push_back(j);
            dfs(j,dist+1);
            st[j] = false;
            v.pop_back();
        }

    }
}

void solve()
{
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int b;
            cin>>b;
            add(i,b);
            flag[b] = 1;
        }
    }
    int yuan = 0;
    for(int i=0;i<n;i++)
    {
        if(flag[i] == 0)
        {
            yuan = i;
            break;
        }
    }
    v.push_back(yuan);
    dfs(yuan,1);
    
    cout<<ans<<endl;
    cout<<res[0];
    for(int i=1;i<res.size();i++)
        cout<<" "<<res[i];


    
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    while(T--)
    {
        solve();
    }
}