代码功能概述

这段 C++ 代码主要实现了一个拓扑排序的应用，用于解决某种课程或事件之间的先后顺序问题，最终计算出完成所有任务所需的最大“层数”（这里的层数可以理解为完成任务的最大先后顺序层级）。

代码详细分析

变量定义

int n,m,l;
int a[1005];
vector<int> s[1005];
map<int, int>mp;
int vis[1005][1005];
int in[1005];
int dis[1005];

• n 和 m：分别表示总任务数和输入的规则数。
• a[1005]：用于临时存储每组规则中的任务编号。
• s[1005]：邻接表，用于存储图的边信息，s[i] 存储从任务 i 出发能到达的所有任务。
• mp：一个 map 容器，用于快速判断某个任务是否在当前规则中。
• vis[1005][1005]：二维数组，用于标记任务之间的边是否已经存在，避免重复添加。
• in[1005]：数组，用于记录每个任务的入度（即有多少条边指向该任务）。
• dis[1005]：数组，用于记录从入度为 0 的任务出发，到达每个任务所需的最大层数。

输入处理

cin>>n>>m;
for(int i=1;i<=m;i++){
    mp.clear();
    cin>>l;
    for(int j=1;j<=l;j++){
        cin>>a[j];
        mp[a[j]]=1;
    }
    for(int j=a[1];j<=a[l];j++){
        if(mp.find(j)==mp.end()){
            for(auto it:mp){
                if(vis[j][it.first]==0){
                    vis[j][it.first]=1;
                    s[j].push_back(it.first);
                    in[it.first]++;
                }
            }
        }
    }
}

• 首先读取总任务数 n 和规则数 m。
• 对于每个规则，先清空 map，然后读取该规则中的任务数量 l 和具体任务编号，将这些任务编号存入 a 数组并在 map 中标记。
• 接着遍历从 a[1] 到 a[l] 的所有任务编号，如果某个任务编号不在当前规则中（即 mp.find(j)==mp.end()），则将该任务与当前规则中的所有任务建立有向边，同时更新 vis 数组、邻接表 s 和入度数组 in。

拓扑排序

int maxx=0;
queue<int> q;
for(int i=1;i<=n;i++){
    if(in[i]==0){
        q.push(i);
        dis[i]=1;
    }
}
while(!q.empty()){
    int x=q.front();
    q.pop();
    maxx=max(maxx,dis[x]);
    for(auto y:s[x]){
        in[y]--;
        dis[y]=max(dis[y],dis[x]+1);
        if(in[y]==0){
            q.push(y);
        }
    }
}

• 初始化一个队列 q，将所有入度为 0 的任务加入队列，并将它们的 dis 值初始化为 1。
• 不断从队列中取出任务，更新最大层数 maxx，并将该任务的所有后继任务的入度减 1。如果某个后继任务的入度变为 0，则将其加入队列，并更新其 dis 值为当前任务的 dis 值加 1。

输出结果

cout<<maxx;
return 0;

输出完成所有任务所需的最大层数。

复杂度分析

• 时间复杂度：$O(m \times k + n + e)$，其中 $m$ 是规则数，$k$ 是每个规则中的任务数，$n$ 是任务总数，$e$ 是图中的边数。
• 空间复杂度：$O(n^2)$，主要用于存储 vis 数组。

注意事项

• 代码假设输入的任务编号范围在 1 到 n 之间。
• 由于使用了 #include<bits/stdc++.h>，该头文件包含了所有标准库的头文件，可能会增加编译时间，在实际项目中建议只包含所需的头文件。

完整代码：

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

// 定义 TaskScheduler 类来处理任务调度问题
class TaskScheduler {
private:
    int n;  // 总任务数
    int m;  // 规则数
    std::vector<int> a;  // 临时存储每组规则中的任务编号
    std::vector<std::vector<int>> s;  // 邻接表，存储图的边信息
    std::map<int, int> mp;  // 用于快速判断某个任务是否在当前规则中
    std::vector<std::vector<int>> vis;  // 二维数组，标记任务之间的边是否已经存在
    std::vector<int> in;  // 记录每个任务的入度
    std::vector<int> dis;  // 记录从入度为 0 的任务出发，到达每个任务所需的最大层数

    // 初始化图和相关数组
    void initGraph() {
        s.resize(n + 1);
        vis.resize(n + 1, std::vector<int>(n + 1, 0));
        in.resize(n + 1, 0);
        dis.resize(n + 1, 0);
    }

    // 处理每条规则，构建图的边
    void processRule(int l) {
        mp.clear();
        a.resize(l + 1);
        for (int j = 1; j <= l; ++j) {
            std::cin >> a[j];
            mp[a[j]] = 1;
        }
        for (int j = a[1]; j <= a[l]; ++j) {
            if (mp.find(j) == mp.end()) {
                for (auto it : mp) {
                    if (vis[j][it.first] == 0) {
                        vis[j][it.first] = 1;
                        s[j].push_back(it.first);
                        in[it.first]++;
                    }
                }
            }
        }
    }

    // 拓扑排序计算最大层数
    int topologicalSort() {
        int maxx = 0;
        std::queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (in[i] == 0) {
                q.push(i);
                dis[i] = 1;
            }
        }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            maxx = std::max(maxx, dis[x]);
            for (auto y : s[x]) {
                in[y]--;
                dis[y] = std::max(dis[y], dis[x] + 1);
                if (in[y] == 0) {
                    q.push(y);
                }
            }
        }
        return maxx;
    }

public:
    // 构造函数，读取输入并初始化相关数据
    TaskScheduler() {
        std::cin >> n >> m;
        initGraph();
        for (int i = 1; i <= m; ++i) {
            int l;
            std::cin >> l;
            processRule(l);
        }
    }

    // 调用拓扑排序函数并返回最大层数
    int getMaxLevel() {
        return topologicalSort();
    }
};

int main() {
    // 创建 TaskScheduler 对象
    TaskScheduler scheduler;
    // 调用 getMaxLevel 方法获取最大层数并输出
    std::cout << scheduler.getMaxLevel() << std::endl;
    return 0;
}