比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 SOBER GOOD BOY 运行时间 0.482 s
代码语言 C++ 内存使用 5.84 MiB
提交时间 2016-10-27 14:26:54
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn=200010;

int N,M,len=0,colr=0,Ans=0;

int head[maxn],du[maxn],chu[maxn],dfn[maxn],f[maxn];

bool vis[maxn];

struct EDGE
{
       int to,next;      
}e[maxn];

void ADD(int x,int y)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     head[x]=len;
}
int  DFS(int x)
{
     //dfn[x]=++tim;
     //if(
     if(vis[x])return f[x];
     //f[x]=1;
     //f[x]++;
     if(!chu[x])
     f[x]++;
     for(int t,i=head[x];i;i=e[i].next)
     {
     t=e[i].to;
     f[x]+=DFS(t);
     } 
     vis[x]=1;
     return f[x];
}
int main()
{
    freopen("chain_2016.in","r",stdin);
    freopen("chain_2016.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int xx,yy,i=1;i<=M;i++)
    { 
    scanf("%d%d",&xx,&yy);
    ADD(xx,yy);du[yy]++;
    chu[xx]++;
    } 
    for(int i=1;i<=N;i++)
    {
            if(!du[i]&&chu[i])Ans+=DFS(i);
    }
    //for(int i=1;i<=N;i++)Ans+=f[i];
    printf("%d",Ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}