Description

出自 IOI 1996

一些学校连接在一个计算机网络上。学校之间存在软件支援协议。每个学校都有它应支援的学校名单（学校 a 支援学校 b，并不表示学校 b 一定支援学校 a）。当某校获得一个新软件时，无论是直接得到还是网络得到，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有连接在网络上的学校都能使用，只需将其提供给一些学校即可。

任务a：

请编一个程序，根据学校间支援协议（各个学校的支援名单），计算最少需要将一个新软件直接提供给多少个学校，才能使软件通过网络被传送到所有学校；

任务b：

如果允许在原有支援协议上添加新的支援关系。则总可以形成一个新的协议，使得此时只需将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件。编程计算最少需要添加几条新的支援关系。

Input

第一行是一个正整数n(2<=n<=100)，表示与网络连接的学校总数。 随后n行分别表示每个学校要支援的学校，即：i+1行表示第i号学校要支援的所有学校代号，最后以0结束。

如果一个学校不支援任何其他学校，相应行则会有一个0。一行中若有多个数字，数字之间以一个空格分隔。

Output

包含两行，第一行是一个正整数，表示任务a的解；第二行也是一个正整数，表示任务b的解。

Sample Input 1

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

Sample Output 1

1
2

题目大意：

强连通分量+缩点，a任务就是要找出缩点后的新图中出度为0的点的数量，任务b为入度点的数量，模板题，这里要注意特判全部连通的情况！

#include<bits/stdc++.h>

using namespace std;

const int maxn = 205;
int dfn[maxn],low[maxn];
int Stack[maxn],t[maxn],tt[maxn],in[maxn],out[maxn];
bool instack[maxn];
int n,tot,num,cnt;
vector<int>e[maxn];

void add_edge(int u , int v)
{
    e[u].push_back(v);
}

void Tar(int u)
{
    dfn[u] = low[u] = ++tot;
    Stack[++num] = u;
    instack[u] = true;
    for(int i = 0 ; i < e[u].size() ; i++)
    {
        int v = e[u][i];
        if(!dfn[v])
        {
            Tar(v);
            low[u] = min(low[u],low[v]);
        }
        else if(instack[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        while(u != Stack[num])
        {
            tt[cnt]++;
            t[Stack[num]] = cnt;
            instack[Stack[num]] = false;
            num--;
        }
        t[Stack[num]] = cnt;
        tt[cnt]++;
        instack[Stack[num]] = false;
        num--;
        cnt++;
    }
}


int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        int v;
        while(cin >> v)
        {
            if(v)
                add_edge(i,v);
            else
                break;
        } 
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(!dfn[i])
            Tar(i);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 0 ; j < e[i].size() ; j++)
        {
            int u = i , v = e[u][j];
            if(t[u] != t[v])
            {
                out[t[u]]++;
                in[t[v]]++;
            }

        }
    }
    int suma = 0 , sumb = 0;
    if(cnt == 1)
    {
        cout << "1\n0" << endl;
        return 0;
    }
    for(int i = 0 ; i < cnt ; i++)
    {
        if(!out[i])
            suma++;
        if(!in[i])
            sumb++;
    }
    cout << sumb << "\n" << max(sumb,suma) << endl;
    return 0;
}