FJUT2541 dp+dfs

dp+dfs"/>

FJUT2541 dp+dfs

.jsp?pid=2541

Seventh大佬是一个爱好学习的学生，他在搞ACM的课余还喜欢搞生物233，这一天他看到了食物链的知识

然后他为了训练同时训练自己的ACM和食物链，给自己的小弟Morning_X出了这么一个题，美名其曰：黑暗森林法则

给出一个N种生物组成的食物网，求食物链的条数。

在这个食物网中，两种生物之间可能存在捕食关系。当然不会出来互相捕食的关系，且不会出现循环的食物网，也就是（A吃B，B吃C，C吃A）

一条食物链定义为：第一种生物是生产者，其他每一种生物捕食前一种生物，且最后的生物是一种最高等级的消费者（最高等级的就是不会被其他动物吃）。

当然，生产者可能有多种，最高等级的消费者也可能有多种。

这个时候就会出现一个套路(ーー゛)，Morning_X当然不会写这个程序啦。按照这个套路，你们需要帮他写一个程序。

Input

第一行输入一个正整数N，表示生物种数；

接下来N行，第N+i行第一个数Ki（0<=Ki<=K），N<=10^5, K<=5；表示生物i被Ki种其他生物捕食，接下来Ki个整数，表示吃生物i的一种生物。

Output

输出一行一个数，表示食物链的条数对10007取模的结果。

SampleInput

4 0 2 1 3 1 1 2 2 3

SampleOutput

3 对样例1进行解释：图中有3条食物链：4-3-1，4-2-1, 4-2-3-1。

题意：很明显的题意了（不解释了）

题解：用vector构造食物链，dp[i[表示到达dfs到第i个点时的食物链数量，最后全部加起来。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector> 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a));
#define lowbit(x)  x&-x;  
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const int maxn = 1e5+5;
const int mod = 1e4+7;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n;
vector<int>v[maxn];
int dp[maxn],fa[maxn];
void dfs(int x){if(v[x].size() == 0){dp[x] = 1;return ;}for(int i = 0; i < v[x].size(); i++){if(!dp[v[x][i]]){dfs(v[x][i]);dp[x] = (dp[x]+dp[v[x][i]])%mod;}else{dp[x] = (dp[x]+dp[v[x][i]])%mod;}}
}
int main() {while(~scanf("%d",&n)){int num;mem(fa,0);mem(dp,0);for(int i = 1; i <= n; i++){scanf("%d",&num);if(!num) fa[i] = 1; while(num--){int x;scanf("%d",&x);v[x].push_back(i);}}int ans = 0;for(int i = 1; i <= n; i++){if(fa[i]){dfs(i);ans = (ans+dp[i])%mod;}}cout<<ans<<endl;}
}