这是一道收缩强连通分量的题。

该题描述的是一个有向图。我们都知道，在一个有向图强连通分量中从任意一个顶点开始，可以到达强连通分量的每个顶点。由此可以把该题中所有强连通分量收缩成分别一个顶点，则入度为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)) 。然后根据点的邻接关系统计出度和入度即可。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2936 KB]
   Test 2: TEST OK [0.000 secs, 2940 KB]
   Test 3: TEST OK [0.000 secs, 2936 KB]
   Test 4: TEST OK [0.000 secs, 2936 KB]
   Test 5: TEST OK [0.011 secs, 2936 KB]
   Test 6: TEST OK [0.011 secs, 2940 KB]
   Test 7: TEST OK [0.011 secs, 2940 KB]
   Test 8: TEST OK [0.000 secs, 2936 KB]
   Test 9: TEST OK [0.000 secs, 2940 KB]
   Test 10: TEST OK [0.000 secs, 2940 KB]
   Test 11: TEST OK [0.000 secs, 2940 KB]

All tests OK.

Your program ('schlnet') produced all correct answers! This is your submission #2 for this problem. Congratulations! 

/*
ID: cmykrgb1
PROG: schlnet
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXN 101
#define max(x,y) ((x)>(y)?x:y)

using namespace std;

ifstream fi("schlnet.in");
ofstream fo("schlnet.out");

int N,M;
int adjl[MAXN][MAXN],fdjl[MAXN][MAXN];
bool vis[MAXN],dis[MAXN][MAXN];
int belong[MAXN],ind[MAXN],oud[MAXN],i0,o0;


void init()
{
    int t,i;
    fi >> N;
    for (i=1;i<=N;i++)
    {
        fi >> t;
        while (t)
        {
            adjl[i][ ++adjl[i][0] ]=t;
            fdjl[t][ ++fdjl[t][0] ]=i;
            fi >> t;
        }
    }
}

void dfs(int i)
{
    int j,k;
    vis[i]=true;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!vis[j])
            dfs(j);
    }
}

void fdfs(int i)
{
    int j,k;
    belong[i]=M;
    for (k=1;k<=fdjl[i][0];k++)
    {
        j=fdjl[i][k];
        if (vis[j] && !belong[j])
            fdfs(j);
    }
}

void solve()
{
    int i,j,k;
    for (i=1;i<=N;i++)
    {
        if (!belong[i])
        {
            dfs(i);
            M++;
            fdfs(i);
            memset(vis,0,sizeof(vis));
        }
    }
    for (i=1;i<=N;i++)
    {
        for (k=1;k<=adjl[i][0];k++)
        {
            j=adjl[i][k];
            dis[belong[i]][belong[j]]=true;
        }
    }
    for (i=1;i<=M;i++)
    {
        for (j=1;j<=M;j++)
        {
            if (i!=j && dis[i][j])
            {
                oud[i]++;
                ind[j]++;
            }
        }
    }
    for (i=1;i<=M;i++)
    {
        if (ind[i]==0)
            i0++;
        if (oud[i]==0)
            o0++;
    }
}

void print()
{
    if (M==1)
        fo << 1 << endl << 0 << endl;
    else
    {
        fo << i0 << endl;
        fo << max(i0,o0) << endl;
    }
    fi.close();
    fo.close();
}

int main()
{
    init();
    solve();
    print();
    return 0;
}