题解 P4017 【最大食物链计数】
图的表示： 由于n的数据规模较大，并且m远远小于n*n，因此，我们采用邻接 表来表示这个图。
寻找食物链： 不难发现，我们从生产者开始，沿着食物链往上搜索，一直搜索 到最高的消费者，那么这就是一条食物链。
生产者和消费者： 那么，我们如何判定生产者和最高级消费者，也即是说如何寻找 搜索的开始和结束？很显然，这个食物网的图是一个有向图，生 产者是其中的没有任何其他节点指向它的结点，而最高消费者是 其中没有指向任何其他结点的点。
判断最高消费者： 显然，最高消费者是很好判断的，当我们搜索到了一个结点，发 现它已经没有指向任何其他的结点让我们继续搜索，那么我们就 找到了一条食物链，并且返回。
判断生产者： 生产者可以在我们建图的时候判断，我们用一个布尔数组来记录 一个结点是否是生产者，首先将这个数组的值全部初始化为 true，然后在建立图的过程中，如果建立一条a指向b的边，那么 显然，我们应该把b置为false，因为已经有一个a指向了它，它 不可能是生产者了。
深度优先搜索： 这里我们采用深度优先搜索，遍历我们的布尔数组，如果是生产 者，我们便开始搜索，当搜索到了最高消费者，我们便找到了一 条食物链，于是ans++(ans用于保存最终结果)，遍历完所有的生 产者，我们也就找到了所有的食物链。
记忆化搜索： 如果按照上面的朴素的搜索，很不幸会tle，因为虽然我们只有 1e5的结点数，但是食物链有大量的交叉，也就是我们会重复搜索 很多已经搜索过的结点，这时，我们就需要采用记忆化的搜索， 已经搜索过的结点的值可以直接用，而不用再重复进行一次搜 索。
我们用一个dp数组来记录之前的搜索结果，dp数组的含义为 1.若dp[i] = -1 ,则表示编号为i的结点未被搜索，需要进行一 次搜索 2.若dp[i] != -1 ，则表示假设编号为i的结点为生产者(其实并 不是)，从i开始的食物链的数量
那么，我们就不难发现，从编号为i的结点开始引出的食物链的数 目，就是所有以它指向的结点为生产者的食物链条数的和
下面我们就可以写代码了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 80112002
struct node
{
int n; //结点点标号
node * next; //指向下一个结点的指针
};//定义链表结点
node v[100005];//邻接表
bool isStart[100005];//判断标号为i的结点是否为生产者
int dp[100005];//保存之前的搜索结果，若为-1，表示需要进行一次搜索，否则表示从
//该节点开始(以它为生产者，其实它不是)的食物链的条数
void insertnode(int a,int b)
{//插入一条a指向b的边，用于建立邻接表
node * t;
t = new node; // new一个结点
t->n = b; // 将结点的点标号置为b
t->next = v[a].next; //将之插入邻接表
v[a].next = t; //将之插入邻接表
isStart[b] = false; //由于a指向b，b不再是生产者，因此将布尔数组置为false
return;
}
int dfs(int x)
{//记忆化搜索，搜索结点的标号为x
int ans;//保存返回值
if(dp[x]!=-1)//如果不为-1，则已经搜索过，可以直接用之前的搜索结果
return dp[x];//返回之前保存在dp中的结果
else if(v[x].next == NULL)
{//如果没有指向其他任何结点，那么是最高消费者，那么从它开始的食物链数目为1
dp[x] = 1;//将dp[x]置为1
return 1;//返回以x为生产者的食物链数目，即1
}
node * p;
p = v[x].next;
ans = 0;//将返回值先初始化为0
while(p!=NULL) //遍历所有x指向的结点
{
ans += dfs(p->n);
ans %= MOD;
/*
从编号为i的结点开始引出的食物链的数目，就是所有以它指向的结点为生产者的食 物链条数的和
*/
p = p->next;
}
dp[x] = ans; //将搜索结果保存在dp数组当中
return dp[x]; // 返回搜索结果
}
int main()
{
int n,m,a,b,ans;
while(cin >> n >> m) //输入n和m
{
for(int i=1;i<=n;i++)
{
/*
将邻接表数组初始化，并且将布尔数组全 部置为true，将dp数组置为-1
*/
v[i].n = i;
v[i].next = NULL;
isStart[i] = true;
dp[i] = -1;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
insertnode(a,b);//将边插入邻接表
}
ans = 0;
for(int i=1;i<=n;i++)
{
if(isStart[i]&&v[i].next!=NULL)
/*如果是生产者并且不是单独的一种孤立生物，那么对它进行搜索*/
ans += dfs(v[i].n) ;
ans %= MOD;
}
printf("%d\n",ans);
}
return 0;
}