Description

Input

Output

一個整數即食物網中的食物鏈條數

Sample Input

Sample Output

思路：

1、一開始在網上還找到了一個公式：食物鏈條數=分叉邊數-分叉點數+1....

尼瑪大騙紙不好用啊、分叉到兩個子樹中就尼瑪不是一個東西了好伐。

2、統計計數問題考慮dp，設定dp【i】表示以i為根的子樹食物鏈的條數。

那這個題就是水題啊，dp【i】=Σdp【v】；

然后設定個超級源點連度為0的所有節點，那么dp【0】就是答案啊。

3、注意孤立節點不算答案啊。就沒了啊。

Ac代碼：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;vector<int >mp[100600];int degree[100600];int dp[100600];int n,m;int Dfs_Dp(int u){    if(dp[u]==-1)    {        dp[u]=0;        int size=mp[u].size();        for(int i=0;i<size;i++)        {            int v=mp[u][i];            dp[u]+=Dfs_Dp(v);        }        if(size==0)dp[u]=1;        return dp[u];    }    else return dp[u];}int main(){    while(~scanf("%d%d",&n,&m))    {        memset(dp,-1,sizeof(dp));        memset(degree,0,sizeof(degree));        for(int i=0;i<=n;i++)mp[i].clear();        for(int i=0;i<m;i++)        {            int x,y;            scanf("%d%d",&x,&y);            mp[x].push_back(y);            degree[y]++;        }        for(int i=1;i<=n;i++)        {            if(degree[i]==0&&mp[i].size()>0)mp[0].push_back(i);        }        if(mp[0].size()>0)        Dfs_Dp(0);        if(dp[0]<0)dp[0]=0;        PRintf("%d/n",dp[0]);    }}