#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10; int n, m; int h[N], e[N], ne[N], idx; int q[N], hh, tt; int d[N], f[N]; void add(int a, int b) // 添加一条边a->b { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } bool topsort() { hh = tt = 0; for (int i = 1; i <= n; i ++ ) if (!d[i]) q[tt ++ ] = i; while (hh != tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if ( -- d[j] == 0) q[tt ++ ] = j; } } return tt == n; } int main() { memset(h, -1, sizeof h); cin >> n >> m; while (m -- ) { int a, b; cin >> a >> b; add(a, b); d[b] ++ ; } if (!topsort()) puts("Impossible"); else { for (int i = n - 1; i >= 0; i -- ) { int j = q[i]; f[j] = j; for (int k = h[j]; k != -1; k = ne[k]) { int u = e[k]; if (f[u] > f[j]) f[j] = f[u]; } } for (int i = 1; i <= n; i ++ ) cout << f[i] ; } return 0; }用tarjan算法实现

这里提供一种使用Tarjan算法实现求解有向无环图（DAG）中最长路径的算法。

Tarjan算法是一种基于深度优先搜索的强连通分量算法，可以用来求解DAG中的最长路径。具体思路是对DAG进行反向拓扑排序，得到的拓扑序列中的每个节点表示原图中的一个强连通分量。然后，从拓扑序列的末尾开始，遍历每个强连通分量，计算该强连通分量中节点的最长路径长度，以此更新所有节点的最长路径长度。

下面是使用Tarjan算法实现的代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], f[N];
int dfn[N], low[N], id[N], sz[N], ts, scc_cnt;
bool in_stk[N];
vector<int> stk;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push_back(u), in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk.back();
            stk.pop_back();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        } while (y != u);
    }
}

bool topsort() {
    vector<int> q;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            if (id[i] != id[k]) d[id[k]]++;
        }
    }
    for (int i = 1; i <= scc_cnt; i++) {
        if (!d[i]) q.push_back(i);
    }
    while (!q.empty()) {
        int u = q.back();
        q.pop_back();
        for (int i = 1; i <= n; i++) {
            if (id[i] == u) f[i] = sz[u];
        }
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (--d[id[v]] == 0) q.push_back(id[v]);
            f[v] = max(f[v], f[u] + sz[id[v]]);
        }
    }
    return scc_cnt == 1;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    if (!topsort()) puts("Impossible");
    else {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = max(res, f[i]);
        }
        cout << res << endl;
    }
    return 0;
}

这里使用了一个vector来模拟栈，dfn、low、id、sz、scc_cnt、in_stk数组分别表示深度优先搜索序号、能到达的最小深度优先搜索序号、每个节点所在的强连通分量编号、每个强连通分量中节点的数量、强连通分量的数量、每个节点是否在栈内。在tarjan函数中，进行深度优先搜索，记录dfn、low、id、sz、scc_cnt、in_stk数组的值。在topsort函数中，调用tarjan函数得到强连通分量，然后根据强连通分量建反图，统计每个强连通分量的入度，将入度为0的强连通分量加入队列中。然后，从队列中依次取出强连通分量，并计算该强连通分量中节点的最长路径长度，以此更新所有节点的最长路径长度。最后，输出所有节点的最长路径长度的最大值即为DAG中的最长路径。