比赛 2024国庆练习1 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 徐诗畅 运行时间 0.553 s
代码语言 C++ 内存使用 6.48 MiB
提交时间 2024-10-04 17:42:15
显示代码纯文本
#include<bits/stdc++.h>
const int mod=1e9+7;
using namespace std;
const int N=100005;
int n,in[N],ans[N];
int cnt,head[N];
struct edge{
	int v,next;
}e[N*10];
void addedge(int u,int v){
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int main(){
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	scanf("%d",&n);
	for(int i = 0;i<=n;i++) head[i]=-1;
	for(int i = 1;i<=n;i++){
		scanf("%d",&in[i]);
		for(int j= 1;j<=in[i];j++){
			int v; scanf("%d",&v);
			addedge(v,i);
		}
	}
	queue<int> q; 
	for(int i = head[0];i!=-1;i=e[i].next){
        int v=e[i].v; in[v]--; ans[v]++;
        if(!in[v]) q.push(v);
    }
    while(!q.empty()){
    	int u = q.front(); q.pop();
    	for(int i = head[u];i!=-1;i=e[i].next){
    		int v=e[i].v;
    		in[v]--;
    		if(!in[v]) q.push(v);
    		ans[v]=(ans[v]+ans[u])%mod;
		}
	}
	printf("%d",ans[n]);
	return 0;
}