说明

本题要求解决两个子任务：

1. 子任务A：计算最少需要多少个学校接收软件副本，才能确保软件传送到所有学校。
2. 子任务B：计算最少需要多少次扩展接收列表，才能确保无论从哪个学校开始分发，软件都能到达所有学校。

算法标签

• 强连通分量（SCC）：使用Tarjan算法识别图中的强连通分量。
• 图论：分析图的入度和出度，解决子任务A和B。
• 贪心算法：选择最优的扩展策略。

解题思路

1. 强连通分量分解：

   • 使用Tarjan算法将图分解为强连通分量（SCC），每个SCC内部的节点互相可达。
   • 统计每个SCC的入度和出度。

2. 子任务A：

   • 最少需要的学校数量等于入度为0的SCC数量。因为这些SCC无法从其他SCC到达，必须直接分发软件。

3. 子任务B：

   • 最少扩展次数等于入度为0的SCC数量和出度为0的SCC数量的最大值。这确保所有SCC都能被访问到。

分析

1. 输入处理：

   • 读取学校数量N。
   • 读取每个学校的接收列表，构建图的邻接表。

2. Tarjan算法：

   • 识别图中的所有强连通分量。
   • 记录每个节点所属的SCC。

3. 统计入度和出度：

   • 遍历所有边，统计每个SCC的入度和出度。

4. 结果计算：

   • 子任务A的结果是入度为0的SCC数量。
   • 子任务B的结果是入度为0和出度为0的SCC数量的最大值。

实现步骤

1. 初始化：

   • 邻接表G存储图的连接关系。
   • 数组dfn、low、stk、vis用于Tarjan算法。
   • 数组indeg和outdeg统计SCC的入度和出度。

2. Tarjan算法：

   • 递归遍历每个节点，识别SCC。
   • 使用栈记录当前路径上的节点。

3. 统计度数：

   • 遍历所有边，更新SCC的入度和出度。

4. 输出结果：

   • 输出入度为0的SCC数量（子任务A）。
   • 输出入度为0和出度为0的SCC数量的最大值（子任务B）。

代码解释

• 邻接表构建：G[i]存储学校i的接收学校列表。
• Tarjan算法：递归遍历节点，识别SCC并记录在belong数组中。
• 度数统计：遍历所有边，更新indeg和outdeg数组。
• 结果输出：根据度数统计结果输出子任务A和B的答案。

该方法通过强连通分量分解和度数分析，高效地解决了软件分发问题，确保在合理时间内计算出最优解。

代码

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <iterator>
#include <list>
#include <cstdio>
#include <iomanip>
#include <climits>
using namespace std;
const int maxn = 200+100;   //点数
int n,indeg[maxn],outdeg[maxn];
int scc, top, tot;
vector<int> G[maxn];
int low[maxn], dfn[maxn], belong[maxn];
int stk[maxn], vis[maxn];
void init(int n) {
    for (int i = 0; i <= n; ++i) {
        G[i].clear();
        low[i] = 0;
        dfn[i] = 0;
        stk[i] = 0;
        vis[i] = 0;
    }
    scc = top = tot = 0;
}
void tarjan(int x) {
    stk[top++] = x;
    low[x] = dfn[x] = ++tot;
    vis[x] = 1;
    for (int i=0; i<int(G[x].size()); ++i) {
        int to=G[x][i];
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x], low[to]);
        } else if (vis[to]) {
            low[x] = min(low[x], dfn[to]);
        }
    }
    if (low[x] == dfn[x]) {
        ++scc;
        int temp;
        do {
            temp = stk[--top];
            belong[temp] = scc;
            vis[temp] = 0;
        } while (temp != x);
    }
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &n);
    int x;
    for(int i=1; i<=n; ++i){
        while(true){
            scanf("%d", &x);
            if(x==0) break;
            G[i].push_back(x);
        }
    }
    for(int i=1; i<=n; ++i) if(!dfn[i]) tarjan(i);
    memset(indeg, 0, sizeof(indeg));
    for(int i=1; i<=n; ++i){
        for(int k=0; k<int(G[i].size()); ++k){
            int j=G[i][k];
            if(belong[i]==belong[j]) continue;
            ++indeg[belong[j]];
            ++outdeg[belong[i]];
        }
    }
    if(scc==1) {
        puts("1");
        puts("0");
    }
    else{
        int in0=0, out0=0;
        for(int i=1; i<=scc; ++i){
            if(indeg[i]==0) ++in0;
            if(outdeg[i]==0) ++out0;
        }
        cout<<in0<<'\n';
        cout<<max(in0, out0)<<'\n';
    }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}