AcWing 3465. 病毒溯源
原题链接
中等
作者:
Ac-Ciallo
,
2024-03-24 12:55:42
,
所有人可见
,
阅读 13
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100;
int n;
//h:头指针链表
//e:元素根节点
//ne:节点的next指针
//idx:计数器
int h[N],e[N],ne[N],idx;
int son[N];//i的儿子节点
bool st[N];//标记i是否是根节点,也就是有没有父节点
void add(int a,int b)//添加一条 a->b 的边
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int x)
{
int rex=0;
son[x]=-1;
for(int i=h[x];~i;i=ne[i])
{
int j=e[i];
int d=dfs(j);
if(rex<d) rex=d,son[x]=j;
else if(rex==d) son[x]=min(son[x],j);
}
return rex+1;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d\n",&n);
for(int i=0;i<n;i++)
{
int cnt; scanf("%d",&cnt);
while(cnt--)
{
int x; scanf("%d",&x);
add(i,x); st[x]=true;//x有父节点,标记
}
}
int root=0; //根节点
while(st[root]) root++;
printf("%d\n",dfs(root));
printf("%d",root);
while(son[root]!=-1)
{
root=son[root];
printf(" %d",root);
}
return 0;
}