Network of Schools

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13046		Accepted: 5215

A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B 
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

5

2 4 3 0

4 5 0

0

0

1 0

1

2

题目大意：

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#define N 110

using namespace std;

vector<vector<int> >G;

int low[N], dfn[N], di[N], maps[N][N];

int Stack[N], n, top, Time, cnt;

bool Instack[N];

void Init()

{

    G.clear();

    G.resize(n + );

    memset(low, , sizeof(low));

    memset(dfn, , sizeof(dfn));

    memset(Stack, , sizeof(Stack));

    memset(di, , sizeof(di));

    memset(Instack, false, sizeof(Instack));

    Time = top = cnt = ;

}

void Tarjan(int u)

{

    int i, v, len;

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

    Stack[top++] = u;//进栈

    Instack[u] = true;

    len = G[u].size();

    for(i =  ; i < len ; i++)//遍历入栈节点的边

    {

        v = G[u][i];

        if(!dfn[v])//点v未被访问过则则对其进行Tarjan

        {

            Tarjan(v);

            low[u] = min(low[u], low[v]);// 回溯的时候改变当前节点的low值

        }

        else if(Instack[v])//如果新搜索到的节点已经被搜索过而且现在在栈中

            low[u] = min(low[u], dfn[v]);//更新当前节点的low值，这里的意思是两个节点之间有一条可达边，而前面节点已经在栈中，那么后面的节点就可能和前面的节点在一个联通分量中

    }

    if(dfn[u] == low[u])//最终退回来的时候 low == dfn ， 没有节点能将根节点更新，那 low == dfn 的节点必然就是根节点

    {

        do

        {

            v = Stack[--top];//出栈

            Instack[v] = false;

            di[v] = cnt;//表示点v在第cnt个强联通分量里

        }

        while(v != u); //一直出栈到此节点， 这些元素是一个强联通分量

        cnt++;//联通分量的个数

    }

}//Tarjan的记过得到di数组记录每个节点分别属于哪个强联通分量

void Solve()

{

    int i, j, In[N], Out[N], in = , out = ;

    memset(In, , sizeof(In));

    memset(Out, , sizeof(Out));

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

        if(!low[i])

            Tarjan(i);

    for(i =  ; i <= n ; i++)// 遍历每条边，找到缩点之后的边

    {

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

        {

            if(i == j)

                continue;

            if(maps[i][j] && di[i] != di[j])//如果i，j两点有边且不属于一个联通分量的边

            {

                Out[di[i]]++;//缩点后出度+1

                In[di[j]]++;//缩点后入读+1

            }

        }

    }

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

    {

        if(!In[i])

            in++;

        if(!Out[i])

            out++;

    }//in表示入度为0的点的个数，out表示出度为0的点的个数

    if(cnt == )//注意当联通分量只有一个时，不应该加边

        printf("1\n0\n");

    else

        printf("%d\n%d\n", in, max(in, out));

}

int main()

{

    int i, a;

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

    {

        Init();

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

        {

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

            {

                G[i].push_back(a);

                maps[i][a] = ;

            }

        }

        Solve();

    }

    return ;

}