学步园

Description

Input

Output

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1
2

    题目大意：有n个学校，学校之间可以传递信息，例如学校 a 可以 传达信息给 b ， 即a ——> b , 但 b 不一定 能传递信息给 a 。 告诉你每个学校能够向哪些学校传递信息，然后有两个问题：

    问题一：至少要向几个学校传递 原始 信息，才能保证所有学校都能收到信息。

    问题二：至少要添加多少组关系（每组关系类型如右：a 可以 向 b 传递信息），才能保证 给任意一个学校原始信息后，其他所有学校都能收到信息。

    解题思路：这道题其实就是一个有n个顶点的有向图，先用 tarjan 缩点 ， 然后分别统计出 入度为0 和 出度为0 的强连通分量个数ansA 和 ansB，那么， 问题一的答案就是ansA , 问题二的答案就是max（ansA ， ansB），但是有特例：当只有一个强连通分量时，问题二的答案就是0 。

    下面用两张图来说明一下问题二的连边方式：

    请看代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 105 ;
vector<int> G[MAXN] ;
int id[MAXN] ; // 记录缩点后每个顶点所属的强连通分量
int tmpdfn ;
int low[MAXN] ;
int dfn[MAXN] ;
int stap[MAXN] ; // 模拟栈
bool vis[MAXN] ;
int ind[MAXN] ; // 统计每个强连通分量的入度
int od[MAXN] ;  // 统计每个强连通分量的出度
int top ;
int component ; // 统计强连通分量数量
int n ;
int ansA ;
int ansB ;
const int INF = 0x7fffffff ;
void chu()
{
    int i ;
    for(i = 0 ; i <= n ; i ++)
        G[i].clear() ;
    mem(id , -1) ;
    mem(dfn , 0) ;
    mem(low , 0) ;
    mem(vis , 0) ;
    mem(od , 0) ;
    mem(ind , 0) ;
    component = 0 ;
    tmpdfn = 0 ;
    top = - 1 ;
}
void init()
{
    chu() ;
    int i ;
    for(i = 1 ; i <= n ; i ++)  // 建图
    {
        int b ;
        for(;;)
        {
            scanf("%d" , &b) ;
            if(b == 0)
                break ;
            G[i].push_back(b) ;
        }
    }
}
void tarjan(int u)
{
    vis[u] = true ;
    stap[++ top] = u ;
    dfn[u] = low[u] = ++ tmpdfn ;
    int i ;
    for(i = 0 ; i < G[u].size() ; i ++)
    {
        int v = G[u][i] ;
        if(!vis[v])
        {
            tarjan(v) ;
            low[u] = min(low[u] , low[v]) ;
        }
        else
        {
            low[u] = min(dfn[v] , low[u]) ;
        }
    }
    if(low[u] == dfn[u])  // 缩点
    {
        ++ component ;
        int tmp ;
        do
        {
            tmp = stap[top --] ;
            dfn[tmp] = INF ;  // 勿忘此处！！,这里是排除其他连通快的影响 ！！
            id[tmp] = component ;
        }
        while(tmp != u) ;
    }
}
void solve()
{
    ansA = ansB = 0 ;
    bool flag = false ;
    int i ;
    for(i = 1 ; i <= n ; i ++)
    {
        if(!vis[i])  // 注意此处，可能不止一个连通块
        {
            tarjan(i) ;
        }
    }
    int j ;
    for(i = 1 ; i <= n ; i ++)
    {
        for(j = 0 ; j < G[i].size() ; j ++)
        {
            int ta , tb ;
            ta = id[i] ;
            tb = id[ G[i][j] ] ;
            if(ta != tb)
            {
                ind[tb] ++ ;
                od[ta] ++ ;
            }
        }
    }
    for(i = 1 ; i <= component ; i ++)
    {
        if(ind[i] == 0)
            ansA ++ ;
        if(od[i] == 0)
            ansB ++ ;
    }
    if(component == 1)
    {
        ansB = 0 ;
    }
    else
    {
        ansB = max(ansB , ansA) ;
    }
    printf("%d\n%d\n" , ansA , ansB) ;
}
int main()
{
    while (scanf("%d" , &n) != EOF)
    {
        init() ;
        solve() ;
    }
    return 0 ;
}