题目描述
一些学校连接在一个计算机网络上,学校之间存在软件支援协议,每个学校都有它应支援的学校名单(学校 A
支援学校 B
,并不表示学校 B
一定要支援学校 A
)。
当某校获得一个新软件时,无论是直接获得还是通过网络获得,该校都应立即将这个软件通过网络传送给它应支援的学校。
因此,一个新软件若想让所有学校都能使用,只需将其提供给一些学校即可。
现在请问最少需要将一个新软件直接提供给多少个学校,才能使软件能够通过网络被传送到所有学校?
最少需要添加几条新的支援关系,使得将一个新软件提供给任何一个学校,其他所有学校就都可以通过网络获得该软件?
输入格式
第 1
行包含整数 N
,表示学校数量。
第 2..N+1
行,每行包含一个或多个整数,第 i+1
行表示学校 i
应该支援的学校名单,每行最后都有一个 0
表示名单结束(只有一个 0
即表示该学校没有需要支援的学校)。
输出格式
输出两个问题的结果,每个结果占一行。
数据范围
2≤N≤100
样例
输入样例:
5
2 4 3 0
4 5 0
0
0
1 0
输出样例:
1
2
算法1
使用tarjan算法缩点后在拓扑图中找到问题中所希望求的量
最重要的是算法正确性的证明。第一问所求的为入度为0的点的数量还是比较显然的,主要是第二问求最少加多少条边可以让原图变成强连通图。本质上是使用了数学归纳法的思想,令p为入度为0的节点数量,q为出度为0的节点数量。
case 1: 不妨设p>=q:
base case: q==1,此时只需要从出度为0的点向所有入度为0的点连一条边即可
对于一般的情况p>=q>1,找出两对不同的入度为0的点以及出毒为0的点a->c, b->d,此时加入c->b。此时出度以及入度为0的点的个数各减1。由数学归纳法的假设可以得到剩下的图需要加p-1条边即可,所以总共需要p条边。
case 2: 不妨设p<=q:
此时的证明与case 1几乎是完全一模一样。
时间复杂度
这里的时间复杂度就是tarjan算法的时间复杂度,因为最后更新所有强连通块入度以及出度的部分的时间复杂度最多是O(m),所以总体的时间复杂度是O(m+n)
C++ 代码
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = 110, M = N*N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], id[N], time_stamp;
int stk[N], top, scc_cnt, din[N], dout[N];
bool in_stack[N];
int n;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int ver){
dfn[ver] = low[ver] = ++ time_stamp;
stk[++top] = ver, in_stack[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]){
int j = e[i];
if (!dfn[j]){
tarjan(j);
low[ver] = min(low[ver], low[j]);
}
else if (in_stack[j]) low[ver] = min(low[ver], dfn[j]);
}
if (dfn[ver] == low[ver]){
++ scc_cnt;
int y;
do{
y = stk[top--];
in_stack[y] = false;
id[y] = scc_cnt;
}while (y != ver);
}
}
int main(){
scanf("%d", &n);
memset(h, -1, sizeof h);
int b;
for (int i = 1; i <= n; i++)
while (scanf("%d", &b), b){
add(i, b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
// 计算出所有scc的入度
for (int i = 1; i <= n; i++){
for (int j = h[i]; ~j; j = ne[j]){
int k = e[j];
int a = id[i], b = id[k];
if (a != b){
din[b]++;
dout[a]++;
}
}
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= scc_cnt; i++){
if (din[i] == 0) ans1 ++;
if (dout[i] == 0) ans2++;
}
printf("%d\n", ans1);
if (scc_cnt == 1) puts("0");
else printf("%d\n", max(ans1, ans2));
return 0;
}