Network of Schools
Destription
许多学校都与计算机网络相连。这些学校之间已达成协议:每所学校都有一份向其分发软件的学校名单(“接收学校”)。注意,如果
你要编写一个程序,计算必须收到新软件副本的学校的最小数量,以便软件根据协议到达网络中的所有学校(子任务
Input
第一行包含整数
Output
第一行应该包含一个正整数:子任务
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';
/*--------------------------------*/
}