比赛 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;
}