tarjan缩点

#include <bits/stdc++.h>
using namespace std;

const int N=105;
const int M=10005;

int n;
int head[N], E=0; // 邻接表建图
int dfn[N], low[N], ts=0; // tarjan数组
bool vis[N]; // tarjan判断点是否在栈中
stack<int> st; // tarjan辅助栈
int id[N], scc_cnt=0; // 强连通分量
int din[N], dout[N]; // 出度与入度

struct Edge{int v, ne;}e[M];
inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    st.push(u); vis[u]=true;
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){ // 如果是树枝边
            tarjan(v);
            low[u]=min(low[u], low[v]);
        }
        else if(vis[v]){ // 如果是后向边或者横叉边
            low[u]=min(low[u], dfn[v]);
        }
    }
    if(dfn[u]==low[u]){ // 如果当前节点就是回溯的最早点
        ++scc_cnt;
        int j;
        do{
            j=st.top(); st.pop(); vis[j]=false; id[j]=scc_cnt; 
        }while(j!=u);
    }
}

int main(){
    memset(vis, 0x00, sizeof vis);
    memset(id, 0x00, sizeof id);
    memset(dfn, 0x00, sizeof dfn);
    memset(low, 0x00, sizeof low);
    memset(din, 0x00, sizeof din);
    memset(dout, 0x00, sizeof dout);
    memset(head, -1, sizeof head);
    cin>>n;

    for(int i=1; i<=n; ++i){
        int b;
        while(cin>>b, b) add(i, b);
    }

    // tarjan找出scc
    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=e[j].ne){
            int a=id[i], b=id[e[j].v];
            if(a!=b) {dout[a]++, din[b]++;}
        }
    }


    // 统计
    int a=0, b=0;
    for(int i=1; i<=scc_cnt; ++i){
        if(!din[i]) ++a; // 统计入度为0的点
        if(!dout[i]) ++b; // 统计出度为0的点
    }

    cout<<a<<endl;
    if(scc_cnt==1) cout<<0<<endl; // 如果缩点
    else cout<<max(a, b);    
    return 0;
}