比赛 2024暑假C班集训E 评测结果 TTTATAAAAA
题目名称 灾难 最终得分 60
用户昵称 123 运行时间 8.281 s
代码语言 C++ 内存使用 4.67 MiB
提交时间 2024-07-14 11:28:44
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=65555;
int head[N*2],nxt[N*2],idx[N*2],val[N*2],val1[N*2],n,tot=0,flag[N*2];
void add(int x,int y)
{
    idx[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    val[y]++;
}
int dfs(int now)
{
    int ret=1;
    flag[now]=1;
    for (int i=head[now];i;i=nxt[i])
    {
        val1[idx[i]]--;
    }
    for (int i=head[now];i;i=nxt[i])
    {
        int y=idx[i];
        if (val1[y]==0 && !flag[y])
        {
            ret+=dfs(y);
        }
    }
    return ret;
}
int main() {
    freopen("catas.in","r",stdin);
    freopen("catas.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int x;
        while (scanf("%d",&x))
        {
            if (!x) break;
            add(x,i);
        }
    }
    cout<<endl;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            val1[j]=val[j];
            flag[j]=0;
        }
        printf("%d\n",dfs(i)-1);
    }
}