Aimeeeeeeeeeeeeeeeeeeeeeeeeee

很简单的东西

就是用tarjan缩个点，然后对于这个新图，考虑入读和出度为1的点就行了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int x;
int head[10000],headd[10000];
stack<int> s;
int dfn[10000],low[10000];
int num[10000];
int chu[10000];
struct b{
    int to;
    int ne;
}ed[5000010],edd[5000001];
int ru[10000];
int xx,yy;
int Aimee;
void add(int f,int to){
    Aimee++;
    ed[Aimee].ne=head[f];
    ed[Aimee].to=to;
    head[f]=Aimee;
    return ;
}
void addd(int f,int to){
    Aimee++;
    edd[Aimee].ne=headd[f];
    edd[Aimee].to=to;
    headd[f]=Aimee;
    return ;
}
int Ai;
int Aim;
void dfs(int now){
    dfn[now]=low[now]=++Ai;
    s.push(now);
    for(int i=head[now];i;i=ed[i].ne){
        int v=ed[i].to;
        if(!dfn[v]){
            dfs(v);
            low[now]=min(low[now],low[v]);
        }else{
            if(!num[v]){
                low[now]=min(low[now],dfn[v]);
            }
        }
    }
    if(low[now]==dfn[now]){
        Aim++;
        while(1){
            int tem=s.top();
            s.pop();
            num[tem]=Aim;
            if(tem==now)
            break;
        } 
    }
} 
int Archie; 
int Aimeee;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        while(scanf("%d",&x)&&x!=0){
            add(i,x);
        }
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i])
            dfs(i); 
    }
    Aimee=0;
    for(int i=1;i<=n;++i){
        for(int j=head[i];j;j=ed[j].ne){
            if(num[i]!=num[ed[j].to]){
                addd(num[i],num[ed[j].to]);
                if(ru[num[ed[i].to]]==0){
                }
                ru[num[ed[j].to]]++;
                chu[num[i]]++;
            }
        }
    }
    Archie=0;
    for(int i=1;i<=Aim;++i){
        if(ru[i]==0)
            Aimeee++;
        if(chu[i]==0)
            Archie++;
    }
    cout<<Aimeee<<endl;
    cout<<max(Aimeee,Archie);
    return 0;
}