问题分析

该问题描述了一个单向信息传播网络，其中每所学校可将软件分享给其他学校。目标是解决两个独立问题：

1. 最少需要向多少所学校分发新软件，才能使所有学校最终获得。
2. 至少需要添加多少条单向分享关系（即扩展），使得只需向任意一所学校分发一次软件，即可覆盖全部学校。

这是一个典型的有向图问题，可通过强连通分量（SCC）缩点建模。将原图中每个强连通分量收缩为一个节点，形成一个有向无环图（DAG）。

核心思路

• 第一问：在缩点后的 DAG 中，入度为 0 的连通分量数量即为所需最小初始分发点数。
• 第二问：在缩点后的 DAG 中，若要使整个图变为"从任意一点出发可达全图"，需满足图中仅有一个出度为 0 的连通分量。因此，答案是 max(入度为 0 的分量数, 出度为 0 的分量数)。当整个图已是一个强连通分量时，第二问答案为 0。

算法实现

使用深度优先搜索（DFS）配合栈结构实现 Tarjan 算法求解强连通分量。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
vector<int> graph[MAXN];
int dfn[MAXN], low[MAXN], stk[MAXN], instk[MAXN], top = 0;
int comp_id[MAXN], comp_cnt = 0;
int in_degree[MAXN], out_degree[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++comp_cnt;
    stk[++top] = u;
    instk[u] = 1;

    for (int v : graph[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        int w;
        do {
            w = stk[top--];
            instk[w] = 0;
            comp_id[w] = u;
        } while (w != u);
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int x;
        while (cin >> x && x != 0) {
            graph[i].push_back(x);
        }
    }

    // 找强连通分量
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 统计缩点后各分量的入度和出度
    for (int u = 1; u <= n; ++u) {
        for (int v : graph[u]) {
            if (comp_id[u] != comp_id[v]) {
                out_degree[comp_id[u]]++;
                in_degree[comp_id[v]]++;
            }
        }
    }

    int zero_in = 0, zero_out = 0;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) zero_in++;
        if (out_degree[i] == 0) zero_out++;
    }

    // 特殊情况：整个图为一个强连通分量
    if (comp_cnt == 1) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }

    cout << zero_in << endl << max(zero_in, zero_out) << endl;

    return 0;
}