python/TangDou/AcWing/SCC/367.md

## [$AcWing$ $367$. 学校网络](https://www.acwing.com/problem/content/description/369/)

### 一、题目描述
一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 $A$ 支援学校 $B$，并不表示学校 $B$ 一定要支援学校 $A$）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问 **最少** 需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

**最少** 需要 **添加几条新的支援关系**，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

**输入格式**
第 $1$ 行包含整数 $N$，表示学校数量。

第 $2..N+1$ 行，每行包含一个或多个整数，第 $i+1$ 行表示学校 $i$ 应该支援的学校名单，每行最后都有一个 $0$ 表示名单结束（只有一个 $0$ 即表示该学校没有需要支援的学校）。

**输出格式**
输出两个问题的结果，每个结果占一行。

**数据范围**
$2≤N≤100$

**输入样例**：
```cpp {.line-numbers}
5
2 4 3 0
4 5 0
0
0
1 0
```

**输出样例**：
```cpp {.line-numbers}
1
2
```

### 二、题目分析
本题唯一的难点在于结论的推导，推导出结论后直接调用$Tarjan$算法的模板即可解决问题。
首先，至少要将新软件提供给多少个学校，才能保证所有的学校都获得软件。
对于普通的$DAG$而言，只需要将新软件提供给所有入度为$0$的节点，就可以保证所有的学校都获得新的软件。

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230720081718.png)

如图所示，入度为$0$的节点有$1$和$2$，这意味着没有任何节点可以到达$1$和$2$节点，所以至少要提供$2$个新软件才能保证$1$和$2$都获得软件；同时$DAG$中任意一个入度不为$0$的节点都可以从某个入度为$0$的节点出发遍历到，正如树中的根节点一定可以达到树中的任意内部节点一样，所以只要将新软件提供给入度为$0$的节点，图中所有的节点都将获得新软件。

对于一般图而言，将原图采用$Tarjan$算法缩点后会形成新的$DAG$，只需要提供缩点后入度为$0$的节点的个数的新软件，就可以让所有的学校都获得软件。因为缩点后的$SCC$内部节点都是彼此可达的，$SCC$中一个节点能够获取软件。其他节点就也都可以获取到软件。

总而言之，至少需要提供缩点后入度为$0$的节点个数个新软件，就能够使得软件被传递到所有的学校。

第二个问题，至少需要添加几条支援关系，才能够使得将新软件提供给任意一个学校，所有学校都可以获取到该软件。

$SCC$中的节点是彼此可达的，因此我们只需要考虑缩点后的$DAG$中要添加几条有向边，才能够让图变成一个完整的$SCC$。

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230720081937.png)


在之前的分析中，我们知道，任意一个出度为$0$的节点都可以通过某入度为$0$的节点到达，后面我们将入度为$0$的节点称为起点，出度为$0$的节点称为终点。也就是说，每一个终点，都可以由某个起点到达，所以只需要连接每个终点到他们对应的起点，那么起点能够到达的位置，该终点也可以到达，比如连接$5$到$1$，那么$1$原本可以到达的节点，$5$也都可以到达了，同时，由于$5$到$1$的连接，原图中的起点和终点都少了一个，如果再连接$7$到$2$，图中的起点和终点又都少了一个。现在图中只剩下一个出度为$0$的节点也就是$6$，将$6$连接到$1$，此时的图就变成了一个$SCC$，也就是出度和入度为$0$的节点消失了。

因此，我们可以从入度和出度的角度来看待该问题，假设图的初始状态有$m$个入度为$0$的节点和$n$个出度为$0$的节点，我们的目标是添加边将其转化为出度或者入度等于$0$节点的个数为$0$的一个强连通图。正如上面的例子那样，我们增加一条边，最多可以同时减去一个起点和一个终点，如果起点个数$m < n$，那么我们前$m$次消掉了$m$个起点和终点，后$n$ - $m$次消掉了$n - m$个终点，也就是至少$n$次操作才能将原图转换为不存在出度或者入度是$0$节点的图；同理$m > n$时，至少要通过$m$次加边操作才能够实现目标。

不含有出度为$0$和入度为$0$的节点只是强连通图的一个充分条件而已，所以至少要$max(m，n)$次加边操作才能实现目的。

下面证明$max(m，n)$次操作可以将原图转化为强连通图，$m > n$时，我们每次连接一条终点到起点的边就可以消去一个入度为$0$的节点以及一个出度为$0$的节点，这里说的入度为$0$或者出度为$0$节点的个数即使是在加边缩点后依旧是减少的。所以$n$次操作之后只会留下$m - n$个起点，从原先任意一个终点连$m - n$条边到达剩下的起点，之后原图就会转化为一个强连通图；$m < n$的情况也是类似，所以，通过$max(m, n)$次加边操作可以实现目标。

综上所述，至少需要加$max(m, n)$条支援关系，才能够使得将新软件提供给任意一个学校，所有学校都可以获取到该软件。

有了上面的结论，我们只需要对原图做一遍$Tarjan$算法，统计下缩点后入度或者出度为$0$节点的个数即可得出答案。要注意的是，如果原图本身就是一个强连通图，也就是$SCC$数目为$1$时，不需要添加任何支援关系，都可以使得将新软件提供给任意一个学校，所有学校都可以获取到该软件。

### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 10010;

int n;
int dfn[N], low[N], ts;
int stk[N], top;
int in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// Tarjan算法求强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    in_stk[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int x;
        do {
            x = stk[top--];
            in_stk[x] = 0;
            id[x] = scc_cnt;
        } while (x != u);
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i++) {
        int c;
        while (scanf("%d", &c), c) add(i, c); // i支援t
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);

    // 统计缩点后的DAG，此DAG中出度为0、入度为0的点的个数
    for (int u = 1; u <= n; u++)
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            int a = id[u], b = id[v];
            if (a != b)
                dout[a]++, din[b]++;
        }

    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) a++;  // 入度为0的强连通块
        if (!dout[i]) b++; // 出度为0的强连通块
    }

    // 输出入度为0的连通块数量,也就是需要软件的数量
    printf("%d\n", a);

    if (scc_cnt == 1) // 如果只有一个强连通块，不用连边
        puts("0");
    else
        printf("%d\n", max(a, b)); // 输出入度为0与出度为0的连通块最大值
    return 0;
}
```