Tarjan 算法求强连通分量

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>

using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define PI acos(-1)
#define debug(a) cout << (a) << endl
typedef long long ll;
int dir8[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int INF = 0x3f3f3f3fLL;
const long long LLF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXn = 1e4 + 15;
const int mod = 1e9 + 7;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
/************有向图****************/
struct node {
    int u, v, next;
} edge[MAXn];
int head_edge[MAXn];
bool in_Stack[MAXn]; //入栈标记
bool  visit[MAXn];  //遍历标记
int DFN[MAXn]; //第几个被遍历（时间戳
int LOW[MAXn]; //强连通分量中最小时间戳（根节点
int Stack[MAXn]; //栈
int tot_edge; 
int Index;  
int tot_point; //时间戳

void add_edge(int u, int v)
{
    edge[++tot_edge] = { u, v, head_edge[u] };
    head_edge[u] = tot_edge;
}

void init()//初始化
{
    tot_edge = tot_point  = Index = 0;
    mem(in_Stack, 0);
    mem(visit, 0);
    mem(Stack, 0);
    mem(head_edge, 0);
}

void Tarjan(int x)
{
    DFN[x] = LOW[x] = ++tot_point; //更新时间戳
    Stack[++Index] = x; //入栈
    in_Stack[x] = visit[x] = 1; //标记
    for (int i = head_edge[x]; i != 0; i = edge[i].next) { //遍历图
        if (!DFN[edge[i].v]) { //如果没有遍历过
            Tarjan(edge[i].v);  //遍历
            LOW[x] = min(LOW[edge[i].v], LOW[x]); //更新LOW数组
        } else if (in_Stack[edge[i].v]) { //如果遍历过并且在栈里面，直接更新LOW数组
            LOW[x] = min(LOW[edge[i].v], LOW[x]);
        }
    }
    if (DFN[x] == LOW[x]) {//发现是整个强连通分量子树里的最小根
        do{
            printf("%d ",Stack[Index]);
            visit[Stack[Index]]=0;
            Index--;
        }while(x!=Stack[Index+1]);//出栈，并且输出
        printf("\n");
    }
    return;
}
int main()
{
    /* 相应操作  */
    for (int i = 1; i <= n; i++) 
        if (!visit[i]) //如果这个点没遍历过，就遍历一遍，避免遗漏
            Tarjan(i);
    /* 相应操作  */
    return 0;
}