身为一个蒟蒻，由于刷不过[NOI2001]食物链
于是出门左转写了道另一道假的食物链 戳这里
这里的食物链个条数其实就是有向图的路径数（应该是这么说吧，我弱）
思路：
拓扑(Topulogy)（一本正经的话说八道）+宽搜+乱搞+（由于本人很弱，所以想不出来了）……
不用先求拓扑序
一边遍历一边用 f数组 统计路径数
存个图，然后队列遍历，要注意的是单独的一个点不算一条链
所以就第一遍把单独的点处理出去（不进队列）
最后的问题就是累加了
如果这个点出度为0时，就
ans+= f[to]
否则更新f[to]，并再次把to入队
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,nxt;
}b[200010];
int n,t,T;
int head[100010];
int f[100010];
int d[100010];
int ans;
int read()
{
int s=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
s=(s<<1)+(s<<3)+c-'0';
c=getchar();
}
return s;
}
void add(int x,int y)//建边
{
b[++t].to=y;
b[t].nxt=head[x];
head[x]=t;
return;
}
void Topulogy()//假的拓扑（英语不好）
{
int i;
int cur,to;
queue<int>p;
for(i=1;i<=n;i++)//初始化入度为0的点（不包括单独的点）
if(!d[i]&&head[i])//分别判断入度为0和是否是单独的点
{
f[i]=1;//初始化路径数，否则会都是0哦~
p.push(i);
}
while(!p.empty())
{
cur=p.front();p.pop();
for(i=head[cur];i;i=b[i].nxt)
{
to=b[i].to;
d[to]--;
f[to]+=f[cur];
if(d[to]==0)
{
if(!head[to])
ans+=f[to];
else
p.push(to);//只有入度为0且出度不为0时才入队
}
}
}
return;
}
int main()
{
int x,y;
n=read();T=read();
while(T--)
{
x=read();y=read();
add(x,y);//建边
d[y]++;//入度
}
Topulogy();
printf("%d",ans);
return 0;
}