比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 gls1196 运行时间 1.778 s
代码语言 C++ 内存使用 155.21 MiB
提交时间 2016-10-20 18:55:12
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mo=1000000007;
ll n,m,val[maxn],ed=0,ind[maxn],he[maxn];
struct Edge{
	ll v,nx;
	Edge(){;}
	Edge(ll x,ll y){v=x;nx=y;}
}e[maxn*100];
void Add(ll u,ll v){
	e[++ed]=Edge(v,he[u]);he[u]=ed;ind[v]++;
}queue<ll>q;
void Mod(ll &x){x=(x+mo)%mo;}
ll solve(){
	q.push(0);val[0]=1;
	while(!q.empty()){
		ll u=q.front();q.pop();
		for(int i=he[u];i;i=e[i].nx){
			ll v=e[i].v;val[v]+=val[u];Mod(val[v]);
			if(--ind[v]==0)q.push(v);
		}
	}Mod(val[n]);
	return val[n];
}
int main(){
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	scanf("%lld",&n);ll u;
	for(int i=1;i<=n;i++){
		scanf("%lld",&m);
		while(m--){
			scanf("%lld",&u);Add(u,i);
		}
	}
	printf("%lld",solve());
	fclose(stdin);fclose(stdout);return 0;
}