比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
niconicoqaq |
运行时间 |
1.139 s |
代码语言 |
C++ |
内存使用 |
12.97 MiB |
提交时间 |
2016-10-20 19:58:45 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
using namespace std;
#define MAXN 100030
#define MOD 1000000007
struct node
{
int begin,end,next;
}edge[MAXN*11+10];
int cnt,Head[MAXN],n,sum[MAXN],id[MAXN],q[MAXN];
void addedge(int bb,int ee)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
int read()
{
int s=0,fh=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
return s*fh;
}
void Topsort()
{
int head,tail,i,u,v;
sum[0]=1;
head=0;tail=0;
for(i=0;i<=n;i++)if(id[i]==0)q[++tail]=i;
while(head!=tail)
{
head++;if(head==100010)head=0;
u=q[head];
for(i=Head[u];i!=-1;i=edge[i].next)
{
v=edge[i].end;
sum[v]=(sum[v]+sum[u])%MOD;
id[v]--;
if(id[v]==0)
{
tail++;if(tail==100010)tail=0;
q[tail]=v;
}
}
}
}
int main()
{
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
int i,k,j,a;
n=read();
memset(Head,-1,sizeof(Head));cnt=1;
for(i=1;i<=n;i++)
{
k=read();
for(j=1;j<=k;j++)
{
a=read();
id[i]++;addedge(a,i);
}
}
Topsort();
printf("%d",sum[n]%MOD);
fclose(stdin);
fclose(stdout);
return 0;
}