记录编号	172565	评测结果	AAAAAAAAAAA
题目名称	[USACO 5.3] 校园网	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-07-25 15:24:30	内存使用	0.41 MiB

/*输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。接下来 N 行中每行都表示一个接收学校列表（分发列表）。
第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。*/
#define Min(a,b)((a)<(b)?(a):(b))
#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>
#include<cstdlib>

using namespace std;

int n,a,in[110],out[110],tot,ans,sum,s[110],top,scc,c[110];
int first[110],dfn[110],lw[110],e[110][110],ru,ch;
bool ins[110];

struct Edge{
    int qd,zd,next;
}edge[10000];

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        while(a!=0)
        {
            edge[++tot].zd=a;
            edge[tot].qd=i;
            edge[tot].next=first[i];
            first[i]=tot;
            scanf("%d",&a);
        }
    }
}

void tarjan(int x)
{
    dfn[x]=lw[x]=++sum;
    s[++top]=x;ins[x]=1;
    for(int i=first[x];i;i=edge[i].next)
    {
        int zd=edge[i].zd;
        if(!dfn[zd])
        {
            tarjan(zd);
            lw[x]=Min(lw[x],lw[zd]);
        }        
        else
            if(ins[zd])
                lw[x]=Min(lw[x],dfn[zd]);
    }
    if(dfn[x]==lw[x])
    {
        int y;
        scc++;
        do{
            y=s[top];
            ins[y]=0;
            c[y]=scc; 
            top--;
        }while(x!=y);
    }
}

void specialjudge()
{
     if(scc==1)
     {    
          printf("1\n0");     
          exit(0);    
     }

}

int main()
{
    freopen("schlnet.in","r",stdin);
	freopen("schlnet.out","w",stdout);
    init();
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=tot;i++)
    {
        if(c[edge[i].qd]!=c[edge[i].zd])
            e[c[edge[i].qd]][c[edge[i].zd]]=1;
    }
    specialjudge();
    for(int i=1;i<=scc;i++)
        for(int j=1;j<=scc;j++)
            if(e[i][j]==1)
            {
                in[j]++;
                out[i]++;
            }
    for(int i=1;i<=scc;i++)
    {
        if(!in[i])
          ru++;
        if(!out[i])
          ch++;
    }
    printf("%d\n%d",ru,Max(ru,ch));
    //while(1);
}