比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 灰里城 运行时间 1.021 s
代码语言 C++ 内存使用 9.09 MiB
提交时间 2016-10-20 19:30:57
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define mod 1000000007
const int maxn=100010;

int tot=0,head[maxn],ru[maxn];
struct E{
	int to,nxt;
}e[maxn*10];
int sum[maxn];
queue<int> q;

int read(){
	char c; int x,f=1;
	while(c=getchar(),c<'0'||c>'9')
		if(c=='-')f=-1;
	x=(c^'0');
	while(c=getchar(),c>='0'&&c<='9')
		x=(x<<3)+(x<<1)+(c^'0');
	return x*f;
}
void Add(int s,int t){
	e[++tot].to=t; e[tot].nxt=head[s]; head[s]=tot;
}
int main(){
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	int n=read();
	for(int i=1;i<=n;++i){
		int k=read();
		for(int j=1;j<=k;++j){
			int x=read();
			Add(x,i); ++ru[i];
		}
	}
	q.push(0); sum[0]=1;
	while(!q.empty()){
		int s=q.front(); q.pop();
		for(int i=head[s];i;i=e[i].nxt){
			int t=e[i].to;
			sum[t]=(sum[t]+sum[s])%mod; --ru[t];
			if(!ru[t])q.push(t);
		}
	}
	printf("%d\n",sum[n]);
//	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}