一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不一定也在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
格式
PROGRAM NAME: schlnet
INPUT FORMAT输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
OUTPUT FORMAT
你的程序应该在输出文件中输出两行。第一行应该包括一个正整数：子任务 A 的解。第二行应该包括子任务 B 的解。
SAMPLE INPUT (file schlnet.in)
5
2 4 3 0
4 5 0
0
0
1 0
SAMPLE OUTPUT (file schlnet.out)
1
2
分析：(转byvoid)
这是一道收缩强连通分量的题。
该题描述的是一个有向图。我们都知道，在一个有向图强连通分量中从任意一个顶点开始，可以到达强连通分量的每个顶点。由此可以把该题中所有强连通分量收缩成分别一个顶点，则入度为0的顶点就是最少要接受新软件副本的学校。
第二问就是，问至少添加多少条边，才能使原图强连通。也就问在收缩后的图至少添加多少条边，才能使之强连通。
可以知道，当存在一个顶点入度为0或者出度为0的时候，该图一定不是强连通的。为了使添加的边最少，则应该把入度为0顶点和出度为0的顶点每个顶点添加1条边，使图中不存在入度为0顶点和出度为0的顶点。
当入度为0的顶点多于出度为0的顶点，则应添加的边数应为入度为0的顶点的个数。当出度为0的顶点多于出入度为0的顶点，则应添加的边数应为出度为0的顶点的个数。
这样就可以解决问题了。但是不要忘了还有特殊的情况，当原图本身就是强连通分量时，收缩成一个顶点，该顶点入度和出度都为0，但第一问应为1，第二问应为0。
求强连通分量，我用的两遍深搜的Kosaraju算法，时间复杂度为O(n)。把找到的每个强连通分量收缩为一的顶点，组成新图。设r(x)为x所在的强连同分量的代表节点，如果原图中存在边e(x,y)，那么新图中有边e(r(x),r(y)) 。然后根据点的邻接关系统计出度和入度即可。
【参考程序】：
/*
ID: XIONGNA1
PROG: schlnet
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
int g1[101][101],g2[101][101];
int into[101],out[101],belong[101];
bool vis[101],dis[101][101];
int n,m,I0,O0;
void g1dfs(int k)
{
vis[k]=true;
for (int i=1;i<=g1[k][0];i++)
if (!vis[g1[k][i]])
g1dfs(g1[k][i]);
}
void g2dfs(int k)
{
belong[k]=m;
for (int i=1;i<=g2[k][0];i++)
if (vis[g2[k][i]] && !belong[g2[k][i]])
g2dfs(g2[k][i]);
}
void solve()
{
memset(vis,false,sizeof(vis));
memset(belong,0,sizeof(belong));
m=0;
for (int i=1;i<=n;i++)
if (belong[i]==0)
{
g1dfs(i);
m++;
g2dfs(i);
memset(vis,false,sizeof(vis));
}
memset(dis,false,sizeof(dis));
for (int i=1;i<=n;i++)
for (int j=1;j<=g1[i][0];j++)
dis[belong[i]][belong[g1[i][j]]]=true;
memset(into,0,sizeof(into));
memset(out,0,sizeof(out));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
if (i!=j && dis[i][j])
{
into[j]++;
out[i]++;
}
I0=0;O0=0;
for (int i=1;i<=m;i++)
{
if (into[i]==0) I0++;
if (out[i]==0) O0++;
}
}
void cout_ans()
{
if (m==1) printf("1\n0\n");
else
{
printf("%d\n",I0);
if (I0>O0) printf("%d\n",I0);
else printf("%d\n",O0);
}
}
int main()
{
freopen("schlnet.in","r",stdin);
freopen("schlnet.out","w",stdout);
scanf("%d",&n);
memset(g1,0,sizeof(g1));
memset(g2,0,sizeof(g2));
int x;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
while (x)
{
g1[i][++g1[i][0]]=x;
g2[x][++g2[x][0]]=i;
scanf("%d",&x);
}
}
solve();
cout_ans();
return 0;
}