提供一种纯dfs回溯的做法。
//把根找出来
#include<bits/stdc++.h>
using namespace std;
int n,idx,maxn,root;
int head[100010],ans[100010],temp[100010],ye[100010],vis[100010];
struct node{
int nxt,to;
}edge[100010];
void add(int u,int v)
{
edge[++idx].nxt=head[u];
edge[idx].to=v;
head[u]=idx;
}
void dfs(int x,int len)
{
if(!ye[x])//一定是到叶子节点再判断
{
if(len==maxn)
{
int flag=0;//判断字典序
for(int i=1;i<=len;i++)
{
if(temp[i]<ans[i])
{
flag=1;
break;
}
if(temp[i]>ans[i])
break;
}
if(flag==1)
{
for(int i=1;i<=len;i++)
{
ans[i]=temp[i];
}
}
}
if(len>maxn)
{
maxn=len;
for(int i=1;i<=idx;i++)
{
ans[i]=temp[i];
}
}
}
for(int i=head[x];i;i=edge[i].nxt)
{
int v=edge[i].to;
temp[len]=v;
dfs(v,len+1);//搜索与回溯
temp[len]=0;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int m;
scanf("%d",&m);
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
add(i,x);
vis[x]=1;//x不可能是根
ye[i]=1;//不是叶子节点
}
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
ans[0]=root;
dfs(root,1);
cout<<maxn<<endl;
for(int i=0;i<maxn;i++)
{
if(i==maxn-1)
printf("%d",ans[i]);
else printf("%d ",ans[i]);
}
return 0;
}