比赛 2024国庆练习1 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 小金 运行时间 0.712 s
代码语言 C++ 内存使用 6.92 MiB
提交时间 2024-10-04 16:35:01
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const long long mod=1e9+7;
const int N=100010,M=1000010;
int n,h[N],r[N],v[M],ne[M],tp[N],tot;
long long s[N];
void add(int x,int y)
{
    tot++;
    v[tot]=y;
    ne[tot]=h[x];
    h[x]=tot;
}
void tpp()
{
    queue<int> q;
    for(int i=0;i<=n;i++)
    {
        if(r[i]==0) q.push(i);
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
        tot++;
        tp[tot]=x;
        for(int i=h[x];i;i=ne[i])
        {
            int y=v[i];
            r[y]--;
            if(r[y]==0) q.push(y);
        }
    }
}
int main()
{
    freopen("three_squirrels.in","r",stdin);
    freopen("three_squirrels.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            int a;
            scanf("%d",&a);
            add(a,i);
            r[i]++;
        }
    }
    tot=-1;
    tpp();
    s[0]=1;
    for(int i=0;i<=n;i++)
    {
        int x=tp[i];
        for(int j=h[x];j;j=ne[j])
        {
            int y=v[j];
            s[y]=(s[y]+s[x]%mod)%mod;
        }
    }
    printf("%lld",s[n]);
    return 0;
}