题意描述
洛谷链接
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使
\(B\) 在 \(A\) 学校的分发列表中，\(A\) 也不一定在 \(B\) 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务
A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务
B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
解题思路
显然这道题考的是强连通分量。将学校用节点表示，分发关系用有向边表示，接着用
Tarjan 求一遍之后缩点即可。
第一问答案即为缩点后入度为 \(0\)
的节点个数，第二问答案即为入度为 \(0\)
和出度为 \(0\)
的节点数两者的最大值。
代码演示
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
75
76
77
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <stack>
const int MAXN = 100;
int n;
std::vector<int> e[MAXN + 1];
int dfn[MAXN + 1], low[MAXN + 1], num = 0, cnt = 0;
std::stack<int> sta;
int ins[MAXN + 1], c[MAXN + 1];
std::vector<int> scc[MAXN + 1];
std::vector<int> ec[MAXN + 1], ecRev[MAXN + 1];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
sta.push(x);
ins[x] = 1;
for (int each : e[x]) {
if (!dfn[each]) {
tarjan(each);
low[x] = std::min(low[x], low[each]);
} else if (ins[each]) {
low[x] = std::min(low[x], dfn[each]);
}
}
if (dfn[x] == low[x]) {
cnt++;
int y;
do {
y = sta.top();
sta.pop();
ins[y] = 0;
c[y] = cnt, scc[cnt].push_back(y);
} while (x != y);
}
}
int main() {
std::cin >> n;
for (int i = 1, x; i <= n; i++) {
while (scanf("%d", &x) != EOF) {
if (x == 0) break;
e[i].push_back(x);
}
}
memset(dfn, 0, sizeof(dfn));
for (int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
for (int each : e[i]) {
if (c[i] == c[each]) continue;
ec[c[i]].push_back(c[each]);
ecRev[c[each]].push_back(c[i]);
}
}
int count1 = 0, count2 = 0;
for (int i = 1; i <= cnt; i++) {
if (ecRev[i].size() == 0) count1++;
if (ec[i].size() == 0) count2++;
}
count2 = std::max(count1, count2);
if (cnt == 1) count1 = 1, count2 = 0;
std::cout << count1 << std::endl << count2 << std::endl;
return 0;
}
|