题目描述

某病毒可以人传人，且传染能力极强，只要与已感染该病毒的人发生接触即刻感染。
现给定一些感染该病毒的人员接触关系，要求你找出其中最早最长的一条传染链。

输入格式

输入在第一行中给出一个正整数 N（N≤104），即感染病毒的人员总数，从 0 到 N−1 进行编号。

随后 N 行按照编号顺序给出人员接触信息，每行按以下格式描述该人员的接触对象：

1
k 接触人员1 …… 接触人员k

其中 k 是该编号人员接触的其他人总数，后面按照时间先后给出所有接触的人员编号。题目保证传染源头有且仅有一个，且已被感染人员不会与另一个感染人员再接触。

输出格式

第一行输出从源头开始的最早最长传染链长度。

第二行输出从源头开始的最早最长传染链，编号之间以 1 个空格分隔，行首尾不得有多余空格。这里的最早最长传染链是指从源头开始的传染链上的人数最多，且被感染的时间最早。

所谓时间最早指的两个长度相等的传染链{a1,a2,…,an}和{b1,b2,…,bn}，存在 1≤k<n，对于所有的 i (1≤i<k)都满足 ai=bi，且 ak 被感染的时间早于 bk 被感染的时间。

输入样例

1
2
3
4
5
6
7
8
9
10
11
10
0
3 3 4 7
2 1 9
1 6
1 5
0
0
0
2 6 0
1 8

输出样例

1
2
4
2 1 3 6

思路

先用邻接表存储图，没有出现的编号就是传染源，然后 dfs 找出路径即可 。

AC 代码

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
#include<bits/stdc++.h>
using namespace std;
vector<int> v[10010],jg,zj;//存储图、结果序列、遍历时的临时序列
void dfs(int x){
    for(int i=0;i<v[x].size();i++){
    	zj.push_back(v[x][i]);
        dfs(v[x][i]);
        zj.pop_back();
    }
    if(zj.size()>jg.size())jg=zj;//如果找到的传染链长就记下来
}
int main()
{
    int n,bj[10010];//bj数组用来判断是否出现过
    cin >> n;
    for (int i = 0; i < n;i++){//存储图
        int m;
        cin >> m;
        while(m--){
            int x;
            cin >> x;
            v[i].push_back(x);
            bj[x] = 1;
        }
    }
    int BT=0;
    for (int i = 0; i < n;i++){//找到传染源
        if(!bj[i]){
            BT = i;
            break;
        }
    }
    dfs(BT);
    cout << jg.size()+1<<endl<<BT;
    for(auto k:jg){
    	cout<<" "<<k;
	}
    return 0;
}