题目分析与思路提示

1. 核心概念：入度 (In-degree)

在有向图中，一个节点的入度表示有多少条边指向它。 在本题背景下，入度就是 “还有多少个前置任务没完成”。

• 如果一个节点的入度为 0，说明它没有任何未完成的前置任务，可以立刻开始。

2. 算法选择：Kahn 算法 (BFS版拓扑排序)

我们需要模拟“不断完成任务”的过程。

算法流程：

1. 建图与统计：使用邻接表存储图，并统计每个点的初始入度 (in_degree 数组)。
2. 初始入队：将所有初始入度为 0 的节点加入队列 $Q$。这些是第一批可以做的任务。
3. 分层处理 (BFS)：
   • 设置时间计数器 time = 0。
   • 记录已完成的任务数 finished_count = 0。
   • 当队列不为空时：
     • time++。
     • 注意：我们要按“轮”来处理。当前队列里所有的任务都可以在这一轮并行完成。所以我们要记录当前队列的大小 size，然后循环 size 次出队操作。
     • 对于每一个出队的节点 $u$：
       • finished_count++。
       • 遍历 $u$ 的所有邻居 $v$（即依赖 $u$ 的后续任务）。
       • 将 $v$ 的入度减 1（表示 $v$ 完成了一个前置依赖）。
       • 关键判断：如果 $v$ 的入度变成了 0，说明 $v$ 的所有前置都搞定了，将 $v$ 加入队列（下一轮做）。
4. 结果判断：
   • 如果 finished_count == N，说明所有任务都做完了，输出 time。
   • 如果 finished_count < N，说明图中有环（剩下的点入度永远无法减为0），输出 -1。

3. 复杂度分析

• 时间复杂度：所有点进队出队一次，所有边被遍历一次。$O(N + M)$。
• 空间复杂度：邻接表和入度数组，$O(N + M)$。
• 对于 $N=10^5$ 的数据，线性复杂度完全可以通过。

参考代码 (C++14)

/**
 * 题目：大典的编纂 (Compiling the Grand Encyclopedia)
 * 难度：GESP 6级
 * 算法：拓扑排序 (Kahn算法) + BFS分层
 */

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 邻接表：adj[u] 存储 u 的后续任务
vector<int> adj[MAXN];
// 入度数组：in_degree[i] 表示任务 i 还有几个前置没完成
int in_degree[MAXN];

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 1. 建图并统计入度
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // u -> v
        in_degree[v]++;      // v 的入度 +1
    }

    // 2. 将所有初始入度为 0 的节点入队
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    int total_time = 0;
    int finished_count = 0;

    // 3. 开始 BFS 拓扑排序
    while (!q.empty()) {
        total_time++; // 开始新的一轮
        
        // 这一轮可以并行处理的任务数量
        int current_layer_size = q.size();
        
        // 处理这一层的所有任务
        for (int i = 0; i < current_layer_size; ++i) {
            int u = q.front();
            q.pop();
            finished_count++; // 完成一个任务

            // 遍历 u 的后续任务
            for (int v : adj[u]) {
                in_degree[v]--; // 前置任务 u 完成了，v 的限制减 1
                
                // 如果 v 的所有前置都完成了
                if (in_degree[v] == 0) {
                    q.push(v); // v 可以进入下一轮
                }
            }
        }
    }

    // 4. 判断是否有环
    if (finished_count == N) {
        cout << total_time << endl;
    } else {
        // 有环，无法完成所有任务
        cout << -1 << endl;
    }

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。涵盖了链状、DAG、环、森林等情况。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
int solve(int N, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(N + 1);
    vector<int> in_deg(N + 1, 0);
    
    for (const auto& e : edges) {
        adj[e.first].push_back(e.second);
        in_deg[e.second]++;
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (in_deg[i] == 0) q.push(i);
    }

    int time = 0;
    int cnt = 0;

    while (!q.empty()) {
        time++;
        int sz = q.size();
        for(int k=0; k<sz; k++) {
            int u = q.front();
            q.pop();
            cnt++;
            for (int v : adj[u]) {
                in_deg[v]--;
                if (in_deg[v] == 0) q.push(v);
            }
        }
    }

    return (cnt == N) ? time : -1;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<pair<int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; M = 4;
            edges = {{1,2}, {1,3}, {2,4}, {3,5}};
        }
        else if (i == 2) {
            // 样例2 (简单环)
            N = 3; M = 3;
            edges = {{1,2}, {2,3}, {3,1}};
        }
        else if (i == 3) {
            // 链状 (耗时 N)
            N = 100; M = N-1;
            for(int k=1; k<N; k++) edges.push_back({k, k+1});
        }
        else if (i == 4) {
            // 菊花图/扁平图 (耗时 2: 根 -> 叶子)
            N = 100; M = N-1;
            for(int k=2; k<=N; k++) edges.push_back({1, k});
        }
        else if (i == 5) {
            // 森林 (多条互不干扰的链)
            N = 100; M = 50;
            for(int k=1; k<=50; k++) edges.push_back({k*2-1, k*2});
        }
        else if (i == 6) {
            // 复杂 DAG (层数较多)
            N = 1000; M = 2000;
            // 保证无环：只生成 u < v 的边
            for(int k=0; k<M; k++) {
                int u = randRange(1, N-1);
                int v = randRange(u+1, N);
                edges.push_back({u, v});
            }
        }
        else if (i == 7) {
            // 随机有环图
            N = 1000; M = 1500;
            // 先生成一个环
            edges.push_back({1, 2}); edges.push_back({2, 3}); edges.push_back({3, 1});
            // 其他随机
            for(int k=3; k<M; k++) {
                edges.push_back({randRange(1, N), randRange(1, N)});
            }
        }
        else {
            // 大规模测试
            N = 100000; 
            if (i == 8) M = 100000; // 稀疏 DAG
            else if (i == 9) M = 200000; // 稠密 DAG
            else { N = 100000; M = 200000; } // Case 10: 大规模有环

            if (i <= 9) {
                // 生成 DAG：只允许小号指向大号，或者打乱编号映射
                // 这里为了简单，只生成 u < v，必然无环
                for(int k=0; k<M; k++) {
                    int u = randRange(1, N-50);
                    int v = randRange(u+1, min(N, u+50)); // 限制跨度，增加深度
                    edges.push_back({u, v});
                }
            } else {
                // Case 10: 随机生成，大概率有环
                for(int k=0; k<M; k++) {
                    int u = randRange(1, N);
                    int v = randRange(1, N);
                    if(u != v) edges.push_back({u, v});
                }
            }
        }

        // 写入输入
        fin << N << " " << edges.size() << "\n";
        for (const auto& e : edges) {
            fin << e.first << " " << e.second << "\n";
        }

        // 写入输出
        fout << solve(N, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}