AcWing 3465. 病毒溯源
原题链接
简单
作者:
lim342
,
2021-05-01 21:29:07
,
所有人可见
,
阅读 6
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
vector<int> v[10008],t,ans;
int trd[10008];
int maxn=0;
void dfs(int n,int l){
if(v[n].size()==0){
if(maxn<l){
maxn=l;
ans=t;
}
}
for(int i=0;i<v[n].size();i++){
t.push_back(v[n][i]);
dfs(v[n][i],l+1);
t.pop_back();
}
}
int main(){
int n,k,x;
cin>>n;
for(int i=0;i<n;i++){//读入邻接表
cin>>k;
while(k--){
cin>>x;
v[i].push_back(x);
trd[x]++;//结点入度
}
sort(v[i].begin(),v[i].end());//从小到大排序,dfs的时候首先找到的最长链则为最小序列
}
int start=0;
for(int i=0;i<n;i++){
if(trd[i]==0){
start=i;//入度为0则为起始结点
break;
}
}
t.push_back(start);
dfs(start,1);
cout<<maxn<<endl;
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1) cout<<' ';
}
}