比赛 2024国庆练习1 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 wdsjl 运行时间 0.701 s
代码语言 C++ 内存使用 14.12 MiB
提交时间 2024-10-04 16:03:34
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int N = 2000100;

struct E{
	int to,ne;
}e[N];

int h[N],tot;

void add(int u,int v){
	e[tot]={v,h[u]};
	h[u]=tot++;
}

int n,in[N];
long long ans[N];
queue<int> q;

void tpsort(){
	while(q.size()){
		int topp=q.front();
		q.pop();
		for(int i=h[topp];~i;i=e[i].ne){
			int v=e[i].to;
			in[v]--;
			ans[v]=(ans[v]%mod+ans[topp]%mod)%mod;
			if(in[v]==0)q.push(v); 
		}
	}
} 

int main(){
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	memset(h,-1,sizeof(h));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int sum;
		scanf("%d",&sum);
		for(int j=1;j<=sum;j++){
			int x;
			scanf("%d",&x);
			add(x,i);
			in[i]++;
		}
	}
	q.push(0);
	ans[0]=1;
	tpsort();
	printf("%lld",ans[n]);
	return 0;
}