kuangbin-连通图

#include<cstdio>
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
typedef long long ll;
// const ll MOD=998244353;
const int N=1e5+5;
int dfn,n,ecnt,SCC;
int sccno[N],num[N],low[N],belong[N],in[N],out[N],head[N];
bool instack[N];
struct edge{int v,next;}e[N];
void add(int u,int v){
e[ecnt].v=v;e[ecnt].next=head[u];head[u]=ecnt++;
}
stack<int>sta;
void init(){
    ecnt=SCC=dfn=0;
    memset(head,-1,sizeof head);
    memset(in,0,sizeof in);
    memset(out,0,sizeof out);
    memset(belong,0,sizeof belong);
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    memset(sccno,0,sizeof sccno);
    while(!sta.empty())sta.pop();
}
void tarjan(int u){
    num[u]=low[u]=++dfn;
    sta.push(u);
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].v;
        if(!num[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])low[u]=min(low[u],num[v]); 
    }
    if(num[u]==low[u]){
    SCC++;
    while(1){
        int v=sta.top();sta.pop();
        belong[v]=SCC;
        if(v==u)break;
        }
    }
}
void solve(){
    for(int i=1;i<=n;i++)if(!num[i])tarjan(i);
    for(int u=1;u<=n;u++){
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].v;
            if(belong[u]!=belong[v]){
                out[ belong[u] ]++;
                in[ belong[v] ]++;
            }
        }
    }
    int a=0,b=0;
    for(int i=1;i<=SCC;i++){
    if(in[i]==0)a++;
    else if(out[i]==0)b++;
    }
    if(SCC==1)cout<<1<<endl<<0<<endl;
    else cout<<a<<endl<<max(a,b)<<endl;
}
int main(){
    init();
    scanf("%d",&n);
    for(int u=1,v;u<=n;u++){
        while(~scanf("%d",&v),v){
        add(u,v);
        }
    }
    solve();
    system("pause");
    return 0;
}