题解：学校网络问题

一、题目背景

一些学校连接在计算机网络上，存在软件支援协议，每个学校有其应支援的学校名单。当一所学校获得新软件时，会将其传送给它应支援的学校。需要解决两个问题：一是最少将新软件直接提供给多少个学校，能让所有学校都能使用；二是最少添加几条新的支援关系，能使新软件提供给任意一个学校，其他所有学校都能通过网络获得。

二、解题思路

本题通过Tarjan算法找出强连通分量，将每个强连通分量看作一个点（缩点），然后根据缩点后图的入度和出度情况来求解。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、时间戳数组 dfn[N]（记录节点首次访问的时间戳）、追溯数组 low[N]（记录节点或其子孙能追溯到的最早时间戳）、栈数组 stk[N] 及栈顶指针 top、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的入度数组 din[N] 和出度数组 dout[N]。
2. 编写添加边的函数，用于构建邻接表。
3. 实现Tarjan算法函数 tarjan，用于找出图中的强连通分量：
- 更新当前节点的 dfn 和 low 值，并将节点入栈，标记在栈中。
- 遍历当前节点的邻接边，对于未访问的节点，递归调用 tarjan 并更新 low 值；对于已访问且在栈中的节点，更新 low 值。
- 若当前节点的 dfn 和 low 值相等，则表示找到了一个强连通分量，将栈中节点弹出，标记不在栈中，并记录所属强连通分量编号。
4. 在 main 函数中：
- 读取学校数量 n，初始化邻接表。
- 读取每个学校应支援的学校名单，构建图的邻接表。
- 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
- 遍历图的边，统计每个强连通分量的入度和出度。
- 统计入度为 (0) 的强连通分量数量 a 和出度为 (0) 的强连通分量数量 b。
- 第一个问题的答案是入度为 (0) 的强连通分量的数量 a，因为入度为 (0) 的强连通分量需要直接提供软件。
- 对于第二个问题，如果强连通分量数量为 (1)，则不需要添加新的支援关系，输出 (0)；否则，答案是 a 和 b 中的较大值，因为需要添加边将入度为 (0) 和出度为 (0) 的强连通分量连接起来，使图成为一个强连通图。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 110, M = 10010;：定义节点的最大数量（学校数量）和边的最大数量。
3. 变量定义：
   • int n;：表示学校的数量。
   • int h[N], e[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int dfn[N], low[N], timestamp;：dfn[N] 记录节点首次访问的时间戳，low[N] 记录节点或其子孙能追溯到的最早时间戳，timestamp 是时间戳计数器。
   • int stk[N], top;：stk[N] 是栈数组，top 是栈顶指针。
   • bool in_stk[N];：标记每个节点是否在栈中。
   • int id[N], scc_cnt;：id[N] 记录节点所属强连通分量编号，scc_cnt 是强连通分量数量。
   • int din[N], dout[N];：分别记录每个强连通分量的入度和出度。

（二）添加边函数

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点。通过更新邻接表数组，将边的信息存储起来。

（三）Tarjan算法函数

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

1. 初始化当前节点的 dfn 和 low 值为当前时间戳，将节点入栈并标记在栈中。
2. 遍历当前节点的邻接边：
   • 若邻接节点未访问，递归调用 tarjan 函数，并更新当前节点的 low 值为当前 low 值和邻接节点 low 值的较小值。
   • 若邻接节点已访问且在栈中，更新当前节点的 low 值为当前 low 值和邻接节点 dfn 值的较小值。
3. 若当前节点的 dfn 和 low 值相等，说明找到了一个强连通分量：
   • 强连通分量数量加 (1)。
   • 从栈中弹出节点，标记不在栈中，记录所属强连通分量编号。

（四）main 函数

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int t;
        while (cin >> t, t) add(i, t);
    }

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

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                dout[a] ++ ;
                din[b] ++ ;
            }
        }

    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
    {
        if (!din[i]) a ++ ;
        if (!dout[i]) b ++ ;
    }

    printf("%d\n", a);
    if (scc_cnt == 1) puts("0");
    else printf("%d\n", max(a, b));

    return 0;
}

1. 读取学校数量 n，初始化邻接表。
2. 读取每个学校应支援的学校名单，构建图的邻接表。
3. 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
4. 遍历图的边，统计每个强连通分量的入度和出度。
5. 初始化入度为 (0) 的强连通分量数量 a 和出度为 (0) 的强连通分量数量 b，并统计相应数量。
6. 输出第一个问题的答案，即入度为 (0) 的强连通分量的数量 a。
7. 判断强连通分量数量是否为 (1)：
   • 若是，输出 (0)，表示不需要添加新的支援关系。
   • 否则，输出 a 和 b 中的较大值，即最少需要添加的新支援关系数量。
8. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取每个学校支援关系构建邻接表，时间复杂度为 (O(n + m))，其中 (m) 是边的数量。
2. Tarjan算法：每个节点最多被访问一次，每条边最多被遍历一次，时间复杂度为 (O(n + m))。
3. 统计入度和出度以及计算结果：遍历 (n) 个节点和 (m) 条边统计入度和出度，时间复杂度为 (O(n + m))；遍历 (scc_cnt) 个强连通分量统计入度为 (0) 和出度为 (0) 的数量，时间复杂度为 (O(scc_cnt))，(scc_cnt\leq n)。
   总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))。
2. 其他数组：时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N]、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、入度数组 din[N] 和出度数组 dout[N]，空间复杂度均为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。