Network of Schools

Destription

许多学校都与计算机网络相连。这些学校之间已达成协议：每所学校都有一份向其分发软件的学校名单（“接收学校”）。注意，如果 $B$ 在学校 $A$ 的分发列表中，则 $A$ 不一定出现在学校 $B$ 的列表中

你要编写一个程序，计算必须收到新软件副本的学校的最小数量，以便软件根据协议到达网络中的所有学校（子任务 $A$）。作为进一步的任务，我们要确保通过向任意学校发送新软件的副本，该软件将到达网络中的所有学校。为了实现这一目标，我们可能需要增加新成员的接收者名单。计算必须进行的最小扩展数量，以便我们将新软件发送到任何学校，它将到达所有其他学校（子任务 $B$）。一个扩展意味着在一所学校的接收者名单中引入一个新成员。

Input

第一行包含整数 $N$：网络中的学校数量（$2\le N\le 100$）。学校由前 $N$ 个正整数标识。接下来的 $N$ 行中的每一行描述接收器列表。行 $i+1$ 包含学校 $i$ 的接收者的标识符。每个列表都以 $0$ 结尾。一个空列表只在一行中包含一个$0$。

Output

第一行应该包含一个正整数：子任务 $A$ 的解。第二行应该包含子任务 $B$ 的解决方案。

Sample Input

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

Sample Output

1
2

问题在于如何理解 ans1 ans2
ans1=cnt(!rdu[i]) ans2=max(ans1,!cdu[i])

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, dfn[N], low[N], tot, cnt, scc[N], siz[N], top, instk[N], stk[N], cdu[N], rdu[N];
vector<int> e[N];
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;

    for (int y : e[x])
    { //邻接表存图
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])
        {
            low[x] = min(low[x], low[y]);
        }
    }

    if (dfn[x] == low[x])
    {
        int y;
        ++cnt;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        } while (y != x);
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        while (cin >> x && x)
            e[i].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
/*-------------------------------*/
    for (int i = 1; i <= n; i++)
    {
        for (auto v : e[i])
        {
            if (scc[i] != scc[v])
            {
                cdu[scc[i]]++;
                rdu[scc[v]]++;
            }
        }
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (!cdu[i])
            cnt2++;
        if (!rdu[i])
            cnt1++;
    }
    cout << cnt1 << '\n'
         << max(cnt1, cnt2) << '\n';
/*--------------------------------*/
}