https://www.cnblogs.com/Slrslr/p/9578471.html
构造一颗“灭绝树”。即对于灭绝树上的两个点x，y，如果x为y的祖先，则x的灭亡会直接导致y的灭亡也就是说X是Y的食物。下面进行构造：首先进行拓扑排序，然后按照排序的逆序构造，保证对于图中的任意x->{y}，都能使x构造前，{y}已经完成构造。然后找到{y}在灭绝树上面的位置，显然{y}在灭绝树上的公共祖先的灭绝会导致{y}全部灭绝进而导致x灭绝。于是可以求它们的lca，那么lca就是x在灭绝树上面的祖先。最后跑一边dfs统计子树大小即可。实际上，这是求有向图必经点的一个特殊问题（无环），实际上可以直接用支配树解决.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define M 100010
using namespace std;
int n,num1,num2,num3;
int head1[M],head2[M],head3[M],in[M],topo[M],deep[M],ans[M],fa[M][20];
struct point{int to,next;}e1[M<<1],e2[M<<1],e3[M<<1];
void add1(int from,int to)
//from是食主人，TO是被吃的
{
e1[++num1].next=head1[from];
e1[num1].to=to;
head1[from]=num1;
}
void add2(int from,int to)
{
e2[++num2].next=head2[from];
e2[num2].to=to;
head2[from]=num2;
}
void add3(int from,int to)
//from是食主人，TO是被吃的
{
e3[++num3].next=head3[from];
e3[num3].to=to;
head3[from]=num3;
}
void topsort()
{
queue<int>q;
for(int i=1;i<=n;i++)
if(!in[i]) //将没有前置食物的动物加入
q.push(i);
int tot=0;
while(!q.empty())
{
int now=q.front();
q.pop();
topo[++tot]=now;
for(int i=head2[now];i;i=e2[i].next)
{
int to=e2[i].to;
in[to]--;
if(!in[to]) q.push(to);
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
for(int i=18;i>=0;i--)
if(deep[fa[x][i]]>=deep[y])
x=fa[x][i];
if(x==y)return y;
for(int i=18;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs(int x)
{
for(int i=head3[x];i;i=e3[i].next)
{
int to=e3[i].to;
dfs(to);
ans[x]+=ans[to];
}
ans[x]++;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
while(1)
{
int x;
scanf("%d",&x);
//x是第I种动物的食物
if(!x) break;
add1(i,x);
add2(x,i);
in[i]++;//I这种动物的食物有几种
}
}
topsort();
for(int i=1;i<=n;i++)
{
int x=e1[head1[topo[i]]].to;
for(int j=head1[topo[i]];j;j=e1[j].next)
x=lca(x,e1[j].to);//取出所有食物的等级最高的
add3(x,topo[i]);//建立一条边从X到它的食材等级最高的那个
deep[topo[i]]=deep[x]+1;//注意DEEP值最大，说明越是自然界食物链的上层
fa[topo[i]][0]=x;
for(int j=1;j<=18;j++) //由于在不断建树，所以不断建立LCA的准备工作
fa[topo[i]][j]=fa[fa[topo[i]][j-1]][j-1];
}
dfs(0);//统计每个点的子树大小
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]-1);
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12693654.html