python/TangDou/AcWing/TopSort/1192_Tarjan.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 60010;

int dnt[N], low[N], id[N], sz[N], timestamp, scc_cnt;
int stk[N], top, in_stk[N];

int dist[N]; //记录强连通分量距离起点的距离
int n, m;

int h[N], hs[N], ne[M], e[M], w[M], idx; // hs[u]为强连通分量建的图的表头
void add(int h[], int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

//有向图的Tarjan算法求强连通分量
void tarjan(int u) {
    low[u] = dnt[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dnt[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j])
            low[u] = min(low[u], dnt[j]);
    }

    if (low[u] == dnt[u]) {
        int x;
        ++scc_cnt;
        do {
            x = stk[top--];
            in_stk[x] = false;
            id[x] = scc_cnt;
            sz[scc_cnt]++;
        } while (x != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    scanf("%d %d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(h, b, a, 1); // b->边权为1的边->a
    }

    //超级源点0号点
    for (int i = 1; i <= n; i++) add(h, 0, i, 100); // 0号点有一条边权100的边到i

    // Tarjan算法求强连通分量(有向图)
    for (int i = 0; i <= n; i++)
        if (!dnt[i]) tarjan(i); //对于每个未访问过的点进行dfs,防止有孤立的点访问不到

    if (scc_cnt != n + 1)
        puts("Poor Xed");
    else {
        for (int u = 0; u <= n; ++u) {
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];

                int a = id[u], b = id[j];
                if (a != b)
                    add(hs, a, b, w[i]); //建新图
            }
        }

        dist[0] = 0;
        //递推求出新建的图中的最长路(按照拓扑序来递推，scc_cnt ~ 1这个顺序符合拓扑序)
        // Tarjan算法本质是一个dfs算法，得到的拓扑序是倒序的，需要倒序枚举
        //拓扑序Topsort本质是一个bfs算法，得到的拓扑序是正序的，需要正序枚举
        for (int u = scc_cnt; u >= 1; u--) {
            //枚举i邻接的所有的边，找出最大的状态转移
            for (int i = hs[u]; ~i; i = ne[i]) {
                int j = e[i];
                dist[j] = max(dist[j], dist[u] + w[i]);
            }
        }
        int res = 0;
        for (int i = 1; i <= scc_cnt; i++) res += (sz[i] * dist[i]);
        printf("%d\n", res);
    }
    return 0;
}