页面历史记录

#define MAXN 1005

int G[MAXN][MAXN]; // 邻接矩阵
int n;             // 顶点数，顶点编号从0开始

int timestamp;  // 时间戳
int dfn[MAXN];  // 第一次遍历到达u的时间戳，至少为1，为0表示u还未被访问过
int low[MAXN];  // 从顶点u开始的DFS遍历能到达的最小时间戳

stack<int> stk;
bool in_stk[MAXN]; // 记录顶点u是否在栈中

int scc_cnt;  // 记录强连通分量的个数，也用于给强连通分量编号
int id[MAXN]; // 记录顶点所属的强连通分量编号

void tarjan_dfs(int u) {
    dfn[u] = low[u] = ++timestamp; // 第一次遍历到u，初始化当前点的时间戳
    stk.push(u);
    in_stk[u] = true;
    for(int i = 0; i < n; i++) { // 遍历所有u能到的邻接点
        if(G[u][i]) {
            if(dfn[i] == 0) { // 如果这个点还没被访问过
                tarjan_dfs(i); // 遍历邻接点
                low[u] = min(low[u], low[i]); // 子结点能到的最小时间戳u能也到
            } else if(in_stk[i]) { // 如果这个点还在栈中，说明这个点比u点先访问到，它的时间戳也应该更早
                low[u] = min(low[u], low[i]); // 用层级更高的点的时间戳更新u的low值
            }
        }
    }
    if(dfn[u] = low[u]) { // 如果u为某个强连通分量的最高点，则可以输出这个强连通分量
        scc_cnt++; // 连通分量数加1
        int tmp;
        do {
            tmp = stk.top();
            stk.pop();
            in_stk[tmp] = false;
            id[tmp] = scc_cnt; // 标记这个点属于哪个强连通分量
        } while(tmp != u);
    }
}

void tarjan() {
    for(int i = 0; i < n; i++) { // 对所有点进行强连通分量计算
        if(dfn[i] == 0) {
            tarjan_dfs(i);
        }
    }
}