|
|
 #include <iostream>
using namespace std;
#define init(I) memset(I,0,sizeof(I))
const int maxn=101;
struct edge
   {
 int data;
edge *next;
 };
edge *g1[maxn],*g2[maxn],*g[maxn];
int vis[maxn],path[maxn],scc[maxn],mark[maxn][maxn];
int out[maxn],in[maxn];
int n,m,cnt;
void add(edge* t[],int s,int e){
edge *p;
p=new edge;
p->data=e;
p->next=t[s];
t[s]=p;
}
void dfs1(int s){
vis[s]=1;
edge *p;
for(p=g1[s];p;p=p->next)
if(!vis[p->data])
dfs1(p->data);
path[0]++;
path[path[0]]=s;
}
void dfs2(int s){
vis[s]=1;
scc[s]=scc[0];
edge *p;
for(p=g2[s];p;p=p->next)
if(!vis[p->data])
dfs2(p->data);
}
void shrink(){
int s,e,k;
init(mark);
edge *p;
for(k=1;k<=n;k++)
for(p=g1[k],s=scc[k];p;p=p->next)
  {
e=scc[p->data];
if(s!=e&&!mark[s][e])
{
mark[s][e]=1;
add(g,s,e);
 }
}
}
void kosaraju()
{
int i;
path[0]=scc[0]=0;
init(vis);
for(i=1;i<=n;i++)
if(!vis[i])
dfs1(i);
init(vis);
for(i=n;i>=1;i--)
{
if(!vis[path[i]])
{
scc[0]++;
dfs2(path[i]);
}
}
}
int main()
{
int to,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
g1[i]=g2[i]=g[i]=NULL;
for(i=1;i<=n;i++)
{
while(scanf("%d",&to)&&to)
{
add(g1,i,to);
add(g2,to,i);
}
}
kosaraju();
shrink();
init(out);
init(in);
int cnt=scc[0];
for(i=1;i<=cnt;i++)
for(j=1;j<=cnt;j++)
if(mark[i][j])
{
out[i]++;
in[j]++;
}
if(cnt==1)
{
printf("1\n0\n");
return 0;
}
int t1=0,t2=0;
for(i=1;i<=cnt;i++)
{
if(in[i]==0) t1++;
if(out[i]==0) t2++;
}
printf("%d\n",t1);
printf("%d\n",t1>t2?t1:t2);
return 0;
}
|