D15 Tarjan SCC 缩点

#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int>G[N];
int tsp, cnt, scc[N], low[N], dfn[N];
stack<int>stk;bool instk[N];

void tarjan(int x)
{
    low[x]=dfn[x]=++tsp;
    stk.push(x);instk[x]=true;
    for(int y:G[x])
    {
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=min(low[x], low[y]);
        }
        else if(instk[y]==true)low[x]=min(low[x], dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        cnt++;
        int z;
        do{
            z=stk.top();stk.pop();instk[z]=false;
            scc[z]=cnt;
        }while(z!=x);
    }
}

int main()
{
    int n;scanf("%d",&n);
    memset(G,0,sizeof(G));
    for(int i=1,j;i<=n;i++)
    {
        while(scanf("%d",&j)&&j)G[i].push_back(j);
    }
    
    tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));
    memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);

    vector<int>cd(cnt+1), rd(cnt+1); 
    for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j]) cd[scc[i]]++, rd[scc[j]]++;
    int  sr=0, sc=0;
    for(int i=1;i<=cnt;i++)
    {
        if(rd[i]==0)sr++;
        if(cd[i]==0)sc++;
    }
    
    int ans=(cnt==1)? 0 : max(sr, sc);
    printf("%d\n%d\n",sr,ans);

    return 0;
}