Tarjan

对于第一问，答案是缩点之后入度为0的点的个数。这个正确性显然。
对于第二问，答案是max(rd==0,cd==0).
为什么？
设rd==0的点的个数为p,cd==0的点为q==0。

1.p<q:
因为每个q都可以被一个p连接，设每个p连接了x个q，那么只要让这个q与p有一条边，那么就可以与这一个p所连的所有点相连。所以此时答案是x1+x2+x3+x4+…xn==q。

2.p>q:
这代表什么呢？说明有一些起点连接了同一个终点，那么设这些起点的对数为x,y=p-x.同第一种情况，首先得把每个终点和一个起点连起来，这时答案是x,然后多的起点要连至他们这一对的其中一个(也就是被终点连的那一个)，所以答案就是x+y=p。
如果有终点连至同一个起点，也可以同第二种情况证明。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,k;
int tot;
int tim;
int top;
int sum;
int clo[N];
int sta[N];
bool vis[N];
int head[4*N];
int rd[N],cd[N];
int dfn[N],low[N];
struct Destiny{
    int u,v;
}des[3*N];
void add(int x,int y){
    des[++tot].u=head[x];
    des[tot].v=y;
    head[x]=tot;
    return ;
}
void tarjan(int now){
    low[now]=dfn[now]=++tim;
    sta[++top]=now;
    vis[now]=1;
    for(int i=head[now];i;i=des[i].u){
        int to=des[i].v;
        if(!dfn[to]){
            tarjan(to);
            low[now]=min(low[now],low[to]);
        }
        else{
            if(vis[to]) low[now]=min(low[now],low[to]);
        }
    }
    if(dfn[now]==low[now]){
        clo[now]=++sum;
        vis[now]=0;
        while(sta[top]!=now){
            clo[sta[top]]=sum;
            vis[sta[top]]=0;
            top--;
        }
        top--;
    }
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        k=1;
        while(k){
            scanf("%d",&k);
            if(!k) break;
            add(i,k);
        }
    }
    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=des[j].u){
            int to=des[j].v;
            if(clo[i]!=clo[to]){
                cd[clo[i]]++;
                rd[clo[to]]++;
            }
        }
    }
    int zeroc=0,zeror=0;
    for(int i=1;i<=sum;++i){
        if(cd[i]==0) zeroc++;
        if(rd[i]==0) zeror++;
    }
    if(sum==1) printf("%d\n%d",zeror,0);
    else printf("%d\n%d",zeror,max(zeroc,zeror));
}