比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
Yuri |
运行时间 |
1.370 s |
代码语言 |
C++ |
内存使用 |
8.48 MiB |
提交时间 |
2016-10-20 19:29:13 |
显示代码纯文本
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100010
#define mod 1000000007
int du[maxn];
int tot, head[maxn];
int cnt[maxn];
queue <int> q;
struct Edge{
int to, nx;
}e[maxn*12];
void edge(int u,int v){
e[++tot].to = v;
e[tot].nx = head[u];
head[u] = tot;
}
void Topo(){
while(!q.empty()){
int x = q.front();q.pop();
for(int i = head[x];i;i = e[i].nx){
int to = e[i].to;
cnt[to] = (cnt[to]+cnt[x])%mod;du[to]--;
if(!du[to]) q.push(to);
}
}
}
int main(){
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
int n;scanf("%d",&n);
cnt[0] = 1;
for(int i = 1,k,a;i <= n;i ++){
scanf("%d",&k);
for(int j = 1;j <= k;j ++){
scanf("%d",&a);edge(a,i);
du[i]++;
}
}
for(int i = 0;i <= n;i ++) if(!du[i]) q.push(i);
Topo();
printf("%d\n",cnt[n]);
getchar();getchar();
return 0;
}