题意：

1.初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。

2.至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

思路：

我们先把图中的强连通分量缩点

经过缩点后，就可以把强连通分量看成一个个独立的点，这张图可以模拟一下，有离散的点，有一些连起来的点，咳咳，但绝对不是连通的!

题目的问题1那不就是在新图上搞一搞出度==0的点的数量

题目的问题2要我们在这张新图上搞一个强连通图，我们可以根据强连通的性质，也就是每个点都要有被指向边和出去的边，那么也就是求一下每个点（强连通分量）的入度和出度，把出度==0的点个数加起来，把入度==0的点个数加起来，比一比谁大，输出谁，因为我们可以直接在入度为0和出度为0的两点间加边，所以取大的那个就满足。

这种题都一个套路。有点水的没意思了。如果没有搞过这种题，可以看我前面两篇blog…当然写的很水，主要可以我是想说可以做做那两题….

#include<iostream>

#include<cstdio>

#include<math.h>

#include<stdlib.h>

#include<vector>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define N 110

int ma[N][N];

int dfn[N];

int low[N];

int stap[N];

int vis[N];

int in[N];

int tp,p,cnt;

int kc[N];

int kr[N];

int n;

void tarjan(int u)

{

    dfn[u]=low[u]=++tp;

    stap[++p]=u;

    vis[u]=1;

    for(int i=1;i<=n;i++)

    {

        if(!ma[u][i])

            continue;

        if(!dfn[i])

        {

            tarjan(i);

            low[u]=min(low[u],low[i]);

        }

        else if(vis[i])

        {

            low[u]=min(low[u],dfn[i]);

        }

    }

    if(dfn[u]==low[u])

    {

        cnt++;

        int temp;

        while(1)

        {

            temp=stap[p];

            vis[temp]=0;

            in[temp]=cnt;

            p--;

            if(temp==u)

            {

                break;

            }

        }

    }

}

void fun()

{

    int pc,pr;

    memset(kc,0,sizeof(kc));

    memset(kr,0,sizeof(kr));

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n;j++)

        {

            if(ma[i][j]&&in[i]!=in[j])

            {

                kr[in[j]]++;

                kc[in[i]]++;

            }

        }

    }

    pc=pr=0;

    for(int i=1;i<=cnt;i++)

    {

        if(!kr[i])

        {

            pr++;

        }

        if(!kc[i])

        {

            pc++;

        }

    }

    if(cnt==1)

    {

        printf("1\n0\n");

    }

    else

        printf("%d\n%d\n",pr,max(pr,pc));

}

void init()

{

    memset(ma,0,sizeof(ma));

    memset(vis,0,sizeof(vis));

    memset(dfn,0,sizeof(dfn));

}

int main()

{

    while(~scanf("%d",&n))

    {

        int x;

        init();

        for(int i=1;i<=n;i++)

        {

            while(scanf("%d",&x)&&x)

                ma[i][x]=1;

        }

        //找强连通分量

        tp=p=cnt=0;

        for(int i=1;i<=n;i++)

        {

            if(!dfn[i])

            {

                tarjan(i);

            }

        }

        fun();

    }

    return 0;

}

/*

5

2 4 3 0

4 5 0

0

0

1 0

*/