p1234

 　　弄了半上午的无向图联通性,高高兴兴的写这个题的时候想起来它是有向图联通性,于是又弄了半上午有向图联通性.中午开始做.

　　仔细看题,它究竟想问什么?想考什么?

　　作为一个无向图,可以直接求强连通分量+缩点,因为强连通分量内部互相可达,不如换成一个点.做第一问的时候,对于这样的新图,可以直接枚举点得到入度为0的点的数量,这些点是没办法靠别人得到软件的.做第二问的时候,要想使得成为一个强连通图,显然需要给所有的零入度的点增加一个入度,给所有零出度的点增加一个出度,然后就互相可达了,因为每个点都有至少一个出度和入度连着其他点.

 　　

using namespace std;
int i,tx,ty,tt,sum,sum1,sum2;
int c[110];
int n,v[110];
int dfn[110],low[110],ru[110],chu[110];
stack<int>zhan;
struct edge{
    int x,y;
    int next;
}e[110];
int tot,head[110];
void add(int x,int y){
    tot++;
    e[tot].x=x;
    e[tot].y=y;
    e[tot].next=head[x];
    head[x]=tot;
}
void tarjan(int now){
    tot++;
    dfn[now]=low[now]=tot;
    zhan.push(now);v[now]=1;
    for(int j=head[now];j;j=e[j].next)
    {
        if(!dfn[e[j].y]){
            tarjan(e[j].y);
            low[now]=min(low[now],low[e[j].y]);
        }
        else if(v[e[j].y])
            low[now]=min(low[now],dfn[e[j].y]);
    }
    if(dfn[now]==low[now]){
        sum++;
        do
        {
            tt=zhan.top();zhan.pop();
            v[tt]=0;
            c[tt]=sum;
        }while(now!=tt);
    }
    return;
}
int main(){
    n=read();
    for(tx=1;tx<=n;tx++){
        ty=read();
        while(ty){
            add(tx,ty);
            ty=read();
        }
    }
    tot=0;//用于记录dfs序
    for(i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=e[j].next){
            if(c[e[j].y]!=c[i]){
                ru[c[e[j].y]]++;
                chu[c[i]]++;
            }
        }
    }
    for(i=1;i<=sum;i++){
        if(ru[i]==0)sum1++;
        if(chu[i]==0)sum2++;
    }
    cout<<sum1<<' '<<(sum==1?0:max(sum1,sum2));
    return 0;
}