采用数组表示法和邻接表存储，实现拓扑排序和关键路径算法

1. 数组表示法实现拓扑排序

拓扑排序是对有向无环图（DAG）进行排序的一种算法，可以用来解决诸如任务调度等问题。拓扑排序算法的基本思想是，将DAG中的节点按照拓扑序列线性排序，使得对于任意的有向边 (u,v)，都有u排在v的前面。

在数组表示法下，可以用一个二维数组来表示一个有向图。假设数组g[i][j]表示从节点i到节点j有一条有向边，则g[i][j]的值为1，否则为0。在进行拓扑排序时，需要统计每个节点的入度，即有多少个节点指向该节点。可以用一个一维数组inDegree来存储每个节点的入度。

具体实现步骤如下：

1. 初始化inDegree数组，对于每个节点i，inDegree[i]表示有多少个节点指向它。
2. 创建一个队列queue，并将所有入度为0的节点加入队列中。
3. 当队列非空时，弹出队首元素u，并将u加入拓扑序列中。
4. 遍历节点u的所有出边，对于每个出边 (u,v)，将inDegree[v]减1。
5. 如果节点v的入度减为0，则将其加入队列queue中。
6. 重复步骤3-5，直到队列为空或所有节点已被加入拓扑序列中。

代码示例：

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

using namespace std;

const int MAXN = 100;   // 最大节点数

int g[MAXN][MAXN];      // 有向图的邻接矩阵表示
int inDegree[MAXN];     // 节点的入度
vector<int> topSort;    // 拓扑序列

void topoSort(int n) {
    queue<int> q;
    // 初始化入度数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j]) {
                inDegree[j]++;
            }
        }
    }
    // 将入度为0的节点加入队列中
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    // 拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topSort.push_back(u);
        for (int v = 0; v < n; v++) {
            if (g[u][v]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;    // 输入节点数和边数
    // 输入每条边的起点和终点
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }
    topoSort(n);      // 进行拓扑排序
    // 输出拓扑序列
    for (int i = 0; i < n; i++) {
        cout << topSort[i] << " ";
    }
    cout << endl;
    return 0;
}

2. 邻接表实现关键路径算法

关键路径是指在完成整个项目的过程中，不能延误的任务路径，即所有任务中最长的路径。关键路径算法可以用来确定项目的总工期和各个任务的最早开始时间和最晚开始时间。

在邻接表表示法下，可以用一个vector数组来表示一个有向图。每个节点的出边用一个pair<int,int>来表示，第一个元素表示边的终点，第二个元素表示边的权值。可以用一个一维数组dis来存储每个节点的最早开始时间和最晚开始时间。

具体实现步骤如下：

1. 初始化dis数组，对于每个节点i，dis[i][0]表示最早开始时间，dis[i][1]表示最晚开始时间。
2. 对整个图进行拓扑排序，得到拓扑序列。
3. 遍历拓扑序列中的每个节点u，对于u的每个出边 (u,v)，更新节点v的最早开始时间dis[v][0]（即max(dis[v][0], dis[u][0]+w(u,v)）），并更新所有后继节点的最晚开始时间dis[v][1]（即min(dis[v][1], dis[u][1]-w(u,v))）。
4. 遍历整个图，找到所有满足dis[i][0]==dis[i][1]的节点i，则i在关键路径上。

其中，w(u,v)表示边(u,v)的权值。

代码示例：

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

using namespace std;

const int MAXN = 100;   // 最大节点数

struct Edge {
    int to;      // 边的终点
    int w;       // 边的权值
};

vector<Edge> g[MAXN];  // 有向图的邻接表表示
int dis[MAXN][2];      // 节点的最早开始时间和最晚开始时间
vector<int> topSort;    // 拓扑序列

void topoSort(int n) {
    queue<int> q;
    // 初始化入度数组
    int inDegree[MAXN] = {0};
    for (int i = 0; i < n; i++) {
        for (auto e : g[i]) {
            inDegree[e.to]++;
        }
    }
    // 将入度为0的节点加入队列中
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    // 拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topSort.push_back(u);
        for (auto e : g[u]) {
            int v = e.to;
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
}

void calcCriticalPath(int n, int start, int end) {
    // 初始化dis数组
    for (int i = 0; i < n; i++) {
        dis[i][0] = dis[i][1] = 0;
    }
    // 计算最早开始时间
    for (int i = 0; i < topSort.size(); i++) {
        int u = topSort[i];
        for (auto e : g[u]) {
            int v = e.to;
            int w = e.w;
            dis[v][0] = max(dis[v][0], dis[u][0] + w);
        }
    }
    // 计算最晚开始时间
    for (int i = topSort.size() - 1; i >= 0; i--) {
        int u = topSort[i];
        if (u == end) {
            dis[u][1] = dis[u][0];
        } else {
            dis[u][1] = INT_MAX;
            for (auto e : g[u]) {
                int v = e.to;
                int w = e.w;
                dis[u][1] = min(dis[u][1], dis[v][1] - w);
            }
        }
    }
    // 输出关键路径
    cout << "Critical Path: ";
    for (int i = 0; i < topSort.size(); i++) {
        int u = topSort[i];
        if (dis[u][0] == dis[u][1]) {
            cout << u << " ";
        }
    }
    cout << endl;
}

int main() {
    int n, m, start, end;
    cin >> n >> m;       // 输入节点数和边数
    cin >> start >> end; // 输入起点和终点
    // 输入每条边的起点、终点和权值
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
    }
    topoSort(n);         // 进行拓扑排序
    calcCriticalPath(n, start, end);   // 计算关键路径
    return 0;
}