求助 9,10,11wa
查看原帖
求助 9,10,11wa
181715
gjh303987897楼主2022/1/25 01:07
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 10001
using namespace std;
int read(){
    char ch=getchar(); int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int n;
struct data{
    int to,next;
}t[10001];
int js,head[10001];
inline void add(int u,int v){
    t[++js].next=head[u];
    t[js].to=v; head[u]=js;
}
int dfn[maxn],num,low[maxn];
int st[maxn],top,co[maxn],col;
void tarjan(int u){
    low[u]=dfn[u]=++num; st[++top]=u;
    for(int i=head[u];i;i=t[i].next){
        int v=t[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!co[v]){
            low[u]=min(dfn[v],low[u]);
        }
    }
    if(low[u]==dfn[u]){
        co[u]=++col;
        while(st[top]!=u){
            co[st[top]]=col;
            top--;
        }
        top--;
    }
}
int vis[maxn];
int main()
{
    n=read(); int s,cnt=1;
    while(1){
        cin>>s; if(s==0) cnt++; if(cnt>n) break;
        if(s!=0) add(cnt,s);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=t[j].next){
            if(co[i]!=co[t[j].to]) vis[co[t[j].to]]++;
        }
    }
    int ans=0;
    for(int i=1;i<=col;i++){
        if(!vis[i]) ans++;
    }
    cout<<ans;
    return 0;
}
2022/1/25 01:07
加载中...