Destription
许多学校都与计算机网络相连。这些学校之间已达成协议：每所学校都有一份向其分发软件的学校名单（“接收学校”）。注意，如果 \(B\) 在学校 \(A\) 的分发列表中，则 \(A\) 不一定出现在学校 \(B\) 的列表中
你要编写一个程序，计算必须收到新软件副本的学校的最小数量，以便软件根据协议到达网络中的所有学校（子任务 \(A\)）。作为进一步的任务，我们要确保通过向任意学校发送新软件的副本，该软件将到达网络中的所有学校。为了实现这一目标，我们可能需要增加新成员的接收者名单。计算必须进行的最小扩展数量，以便我们将新软件发送到任何学校，它将到达所有其他学校（子任务 \(B\)）。一个扩展意味着在一所学校的接收者名单中引入一个新成员。
Input
第一行包含整数 \(N\)：网络中的学校数量（\(2 \leq N \leq 100\)）。学校由前 \(N\) 个正整数标识。接下来的 \(N\) 行中的每一行描述接收器列表。行 \(i+1\) 包含学校 \(i\) 的接收者的标识符。每个列表都以 \(0\) 结尾。一个空列表只在一行中包含一个\(0\)。 ## Output
第一行应该包含一个正整数：子任务 \(A\)
的解。第二行应该包含子任务 \(B\)
的解决方案。 ## Sample Input 1
2
3
4
5
65
2 4 3 0
4 5 0
0
0
1 01
21
2ans1 ans2
ans1=cnt(!rdu[i]) ans2=max(ans1,!cdu[i]) ##
代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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';
/*--------------------------------*/
}