這是一道收縮強連通分量的題。

該題描述的是一個有向圖。我們都知道，在一個有向圖強連通分量中從任意一個頂點開始，可以到達強連通分量的每個頂點。由此可以把該題中所有強連通分量收縮成分別一個頂點，則入度爲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;
}