拓扑排序

介绍

拓扑排序是一种将一个有向无环图变成一个线性序列的算法。

这个序列的要求是：

1. 每个顶点都出现了一次。
2. 对于一条边：$a \to b$，我们要求 $a$ 在 $b$ 的前面。

实现

1. 找到入度为 $0$ 的点，输出。
2. 删除这个点和这个点连着的所有边。
3. 继续重复前两步，直到没有点了。

代码

B3644 【模板】拓扑排序 / 家谱树 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n;
vector <int> v[100005], v2[100005];
int d[100005];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x;
        while (cin >> x) {
            if (x == 0) break;
            else v[x].push_back(i), d[x] ++, v2[i].push_back(x);
        }
    } 
    queue <int> q;
    for (int i = 1; i <= n; i ++) {
        if (v[i].size() == 0) {
            cout << i << " ";
            q.push(i);
        }
    }
    // cout << "*\n" << v2[q.front()].size();
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v2[x].size(); i ++) {
            d[v2[x][i]] --;
            // cout << d[v[x][i]] << " ";
            if (d[v2[x][i]] == 0) {
                cout << v2[x][i] << " ";
                q.push(v2[x][i]);
            } 
        }
    }
    return 0;
}

关键路径

介绍

我们把一个有向无环图想象成一个工程的规划图，必须在完成前一项后才能完成后一项，二千每一个没有关联的项可以同时开工。

关键路径，就是如果增加关键路径中任意一项的时间的话，整个工程的时间就会增加。

实现

关键路径其实就是从入度为 $0$ 的一个点到出度为 $0$ 的一个点的最长路径。

我们可以定义两个数组，一个数组存储从入度为 $0$ 的起点到其他点的最短用时；一个数组存储从出度为 $0$ 的一个点到其他点的最长时间。

具体实现见代码。

如果一个点的最短时间和最长时间是一样的，那么这个点就在关键路径里面。

代码

#include <bits/stdc++.h>
using namespace std;
int a[105][105], e[1005], l[1005], n, in[1005], ou[1005];
vector <int> ed[1005], v[1005], v2[1005], ed2[1005];
int s = 0, t = 0;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> a[i][j];

            if (a[i][j] == 0)
                continue;

            ed[i].push_back(j);
            ed2[j].push_back(i);
            v[i].push_back(a[i][j]);
            v2[j].push_back(a[i][j]);
            in[j] ++, ou[i] ++;
        }
    }

    for (int i = 1; i <= n; i ++) {
//      cout << in[i] << " " << ou[i] << "\n";

        if (in[i] == 0)
            ed[0].push_back(i), s = i;

        if (ou[i] == 0)
            ed[n + 1].push_back(i), t = i;
    }

    queue <int> q;
    q.push(s);

    while (q.size()) {
        int nw = q.front();
        q.pop();

//      cout << nw << " ";

        for (int i = 0; i < ed[nw].size(); i ++) {
            e[ed[nw][i]] = max(e[ed[nw][i]], e[nw] + v[nw][i]);
            in[ed[nw][i]] --;
//          cout << e[ed[nw][i]] << ' ' << in[e[ed[nw][i]]] << "\n";

            if (in[ed[nw][i]] == 0) {
                q.push(ed[nw][i]);
            }
        }
    }

    q.push(t);

    for (int i = 1; i <= n; i ++)
        l[i] = e[t];

    while (q.size()) {
        int nw = q.front();
        q.pop();
//      cout << ed2[nw].size();

        for (int i = 0; i < ed2[nw].size(); i ++) {
            l[ed2[nw][i]] = min(l[ed2[nw][i]], l[nw] - v2[nw][i]);
            ou[ed2[nw][i]] --;
//          cout << 114514 << "\n";

            if (ou[ed2[nw][i]] == 0) {
                q.push(ed2[nw][i]);
            }
        }
    }

    for (int i = 1; i <= n; i ++) {
//      cout << e[i] << " " << l[i] << "\n";

        if (e[i] == l[i])
            cout << i << " ";
    }
}