比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 再见 运行时间 1.366 s
代码语言 C++ 内存使用 9.83 MiB
提交时间 2016-10-20 20:40:23
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cctype>

const long long MOD=1e9+7;

inline int read(){
	int _x=0; char ch; bool flag=false;
	while(ch=getchar(),!isdigit(ch)) ch=='-'?flag=true:false;
	while(_x=_x*10+ch-'0',ch=getchar(),isdigit(ch));
	return flag?-_x:_x;
}

int n,k,tot,Q[100010],qhead,tail,ru[100010],head[100010],next[1000010],to[1000010];
long long ans[100010];

int main()
{
	//freopen("a.txt","r",stdin);
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		k=read();
		for(int j=1;j<=k;j++){
			int x=read();
			++tot;
			to[tot]=i; 
			next[tot]=head[x]; 
			head[x]=tot;
			ru[i]++;
		}
	}
	ans[0]=1;
	for(int i=0;i<=n;i++)
		if(ru[i]==0)
			Q[tail++]=i;
	while(qhead<tail){
		int now=Q[qhead++];
		for(int p=head[now];p;p=next[p]){
			ans[to[p]]=(ans[to[p]]+ans[now])%MOD;
			ru[to[p]]--;
			if(!ru[to[p]]){
				Q[tail++]=to[p];
			}
		}
	}
	printf("%lld",ans[n]);
	return 0;
}