有向图
inline void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
st[++top] = x;vis[x] = 1;
for(rint i = head[x];i;i = e[i].last) {
if(!dfn[e[i].to]) {
tarjan(e[i].to);
low[x] = Min(low[x],low[e[i].to]);
}
else if(vis[e[i].to]) low[x] = Min(low[x],dfn[e[i].to]);
}
if(dfn[x] == low[x]) {
col[x] = ++col[0];
vis[x] = 0;
while(st[top] ^ x) {
col[st[top]] = col[0];
vis[st[top]] = 0;
--top;
}
--top;
}
return ;
}
无向图
inline void tarjan(int x,int da) {
dfn[x] = low[x] = ++cnt;
st[++top] = x;
vis[x] = 1;
for(rint i = head[x];i;i = e[i].last) {
if(e[i].to == da) continue;
if(!dfn[e[i].to]) {
tarjan(e[i].to,x);
low[x] = Min(low[x],low[e[i].to]);
}
else low[x] = Min(low[x],dfn[e[i].to]);
}
if(dfn[x] == low[x]) {
col[x] = ++col[0];
vis[x] = 0;
while(st[top] ^ x) {
col[st[top]] = col[0];
vis[st[top]] = 0;
--top;
}
--top;
}
return ;
}