有向图
强连通分量、缩点
取 cmin(low[u], dfn[v]) 时 v 一定要在栈里。
弹栈时要将 u 也弹出。
int dfn[N], low[N], dfnp, st[N], sp, vis[N], bl[N], blp;
void tarjan(int u) {vis[st[++sp] = u] = 1;dfn[u] = low[u] = ++dfnp;for(int i = hed[u], v; v = e[i].v, i; i = e[i].nxt)if(!dfn[v]) tarjan(v), cmin(low[u], low[v]);else if(vis[v]) cmin(low[u], dfn[v]);if(dfn[u] == low[u]) {int x;blp++;do vis[x = st[sp--]] = 0, bl[x] = blp;while(x ^ u);}
}
无向图
点双、割点
取 cmin(low[u], dfn[v]) 时 v 不用看在不在栈里。
弹栈不用将 u 弹出。
int st[N], sp, dfn[N], low[N], dfnp, np, cut[N], rt;
vec<int> dcc[N];
void tarjan(int u) {st[++sp] = u;dfn[u] = low[u] = ++dfnp;if(!hed[u]) dcc[++np].eb(u);for(int i = hed[u], v, son = 0; v = e[i].v, i; i = e[i].nxt)if(!dfn[v]) {tarjan(v);cmin(low[u], low[v]);if(low[v] == dfn[u]) {if(++son > 1 || u != rt) cut[u] = 1;int x;np++;do dcc[np].eb(x = st[sp--]);while(x ^ v);dcc[np].eb(u);}} else cmin(low[u], dfn[v]);
}
割边（桥）
有重边的代码。
int brg[M << 1], dfn[N], low[N], dfnp;
void tarjan(int u, int eid) {dfn[u] = low[u] = ++dfnp;for(int i = hed[u], v; v = e[i].v, i; i = e[i].nxt)if(!dfn[v]) {tarjan(v, i ^ 1);cmin(low[u], low[v]);if(low[v] == dfn[v]) brg[i] = brg[i ^ 1] = 1;} else if(i != eid) cmin(low[u], dfn[v]);
}