AcWing 3465. 病毒溯源
原题链接
中等
作者:
赜
,
2024-04-19 19:24:44
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010;
int h[N],ne[N],e[N],idx;
int son[N];
int st[N],root;
int n;
void add_edge(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
int res=0;
son[u]=-1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
int d=dfs(j);
if(res<d||res==d&&j<son[u])
{
res=d;
son[u]=j;
}
}
return res+1;
}
int main()
{
memset(h,-1,sizeof(h));
cin>>n;
for(int i=0;i<n;i++)
{
int k;
cin>>k;
while(k--)
{
int x;
cin>>x;
add_edge(i,x);
st[x]=1;
}
}
root=0;
while(st[root]) root++;
cout<<dfs(root)<<endl;
cout<<root;
for(int i=son[root];i!=-1;i=son[i])
cout<<" "<<i;
return 0;
}