写在前面

Tarjan缩点经典问题，证明其他题解已经泛滥了。。。我写一写我自己想法。

技巧（KEYS）

• 任务A：入读为$0$的点的个数
• 任务B: 求入度为$0$的点数与出度为0的点的个数的最大值值。

缩完点之后，可以使用set去除重复的边，进行重新建图。QAQ 好方便！

注意

需要注意缩完点之后，只剩下一个点的情况QAQ不判断会WA一个点

/*!
 * FileName: luogu-2746.cpp
 * This Problem is on luogu. The ID of the problem is 2746. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-08-13 21:37:29 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<stack>
#include<set>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int _N = 110;
const int _M = _N * _N;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int head[_N];
struct edges{
    int node;
    int nxt;
}edge[_M];
int tot = 0;
void add(int u, int v)
{
    edge[++tot].nxt = head[u];
    head[u] = tot;
    edge[tot].node = v;
}
int n;
int dfn[_N];
int low[_N];
int dfnClock = 0;
int scc[_N];
int sccCnt = 0;
stack <int> S;
void tarjan(int now)
{
    low[now] = dfn[now] = ++dfnClock;
    S.push(now);
    for(register int i = head[now];i;i = edge[i].nxt)
    {
        int exNode = edge[i].node;
        if(dfn[exNode] == 0)
        {
            tarjan(exNode);
            low[now] = min(low[now], low[exNode]);
        }
        else if(scc[exNode] == 0)
            low[now] = min(low[now], dfn[exNode]);
    }
    if(low[now] == dfn[now])
    {
        sccCnt ++;
        while(true)
        {
            scc[S.top()] = sccCnt;
            if(S.top() == now)
            {
                S.pop();
                break;
            }
            S.pop();
        }
    }
}
int outd[_N];
int ind[_N];
int main()
{
    n = read();
    for(register int i = 1;i <= n;i++)
    {
        int tmp;
        while(true)
        {
            tmp = read();
            if(tmp == 0) break;
            add(i, tmp);
        }
    }
    for(register int i = 1;i <= n;i++)
        if(dfn[i] == 0)
            tarjan(i);
    set<pair<int,int> > S;
    for(register int i = 1;i <= n;i++)
    {
        for(register int j = head[i];j;j = edge[j].nxt)
        {
            int exNode = edge[j].node;
            if(scc[i] != scc[exNode])
                S.insert(make_pair(scc[i], scc[exNode]));
        }
    }

    for(set<pair<int, int > >::iterator i = S.begin();i != S.end();i++)
    {
        outd[(*i).first] ++;
        ind[(*i).second] ++;
    }
    int ans1 = 0;
    int ans2 = 0;
    for(register int i = 1;i <= sccCnt;i++)
    {
        if(ind[i] == 0)
            ans1 ++;
        if(outd[i] == 0)
            ans2 ++;
    }
    printf("%d\n%d\n", ans1, sccCnt == 1 ? 0 : max(ans1, ans2)) ;
    return 0;
}