天梯赛L2病毒溯源(超详细)

标注:代码出处
https://blog.csdn.net/qq_45728527/article/details/116169693?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%A4%A9%E6%A2%AF%E8%B5%9B%E7%97%85%E6%AF%92&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-3-116169693.142^v9control,157^v4new_style&spm=1018.2226.3001.4187

建议学习一下vector的用法
(挺简单的，其实，比赛常用的)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;//N表示le是less 小于10^4  
vector<vector<int> > g;//存下病毒关系  //动态二维数组 
vector<int> ans,tmp;//存变异链，tmp是本次的路径的数组序列，ans是本次以前的最佳路径序列  
bool vis[N];//标记数组，用于查找根病毒(为true的都是从另一个节点延申出来的，false 的是初始节点)
//(审题:题目保证病毒源头有且仅有一个)

int n,k,cnt=1; //n病毒种类数，k是某病毒的变异株数目，cnt初始化为1，路径最起码是1，记录最长的路径 

void DFS(int u,int sum)  //第一次，u是起点 0 ，sum是1目前的路径最长 
{
    if(sum>cnt)//如果sum大于上一次的cnt值我们就进行替换
    {
        ans = tmp;//ans等于temp，替换为当前的最长路径 
        cnt = sum;//用cnt记录最长的路径长度 
    }
    else if(sum==cnt&&tmp<ans)//sum==cnt时，由于题目要求输出最小序列，所以我们也要进行判断交换
    //!!!!vector直接可以比大小(才学vector，这个真好使) 
    {
        ans = tmp;//ans为结果路径 
    }
    for(int i=0;i<g[u].size();i++)  //该点的邻接点都要遍历  如0的 3个邻接点    6  4 8   
    {
        int v = g[u][i]; //0的第一个邻接点，此题是6 
        tmp.push_back(v);//把它的第一个邻接点插入到那个深度遍历的队列中temp，temp作中间变量 
        DFS(v,sum+1);//递归v，再找v的第一个邻接点(依次递归) ，sum路径加1 
        tmp.pop_back();//回溯，计算这个点u的另外的邻接点(先4,再8)的最长路径 ，
		//直到遍历完u点(0病毒)的所有邻接点，同时已经计算出来最长路径  cnt 
    }
}

int main()
{
    cin>>n;//病毒的种类总数  0 ......n-1 
    g.resize(n+1);//申请空间 //动态二维数组申请内存 
    for(int i=0;i<n;i++)
    {
        cin>>k;//第i个病毒产生的变异毒株的种类数目 
        while(k--)
        {
            int x;     
            cin>>x;
            vis[x] = true;    //vis[6]   vis[4] vis[8]
            //v[] 6 4 8 5  9 7 2 3 1 
            g[i].push_back(x);//6   4  8  
        }
    }
    int root = 0;
    while(vis[root]) root++;//找到根病毒
    
    DFS(root,1);// 0,1 
    
    cout<<cnt<<endl;//从源头开始最长变异链的长度 
    cout<<root;//输出从源头开始最长的一条变异链 
    for(int i=0;i<ans.size();i++)
        cout<<' '<<ans[i];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59