tarjan算法（非完全版）
2021-05-06 22:28
标签：最小 完全 存在 tarjan算法 割点 size 优先 block for 有向图 \(dfn[x]\),在深度优先遍历中，按照每个节点第一次被访问的顺序，依次做整数标记 \(low[x]\),通过非搜索边能到达的最小时间戳 无向边\((x,y)\)是割边/桥，当且仅当存在x的一个子节点满足\(dfn[x] 若x不是根节点，则x是割点当且仅当存在一个子节点y满足\(dfn[x]\leq low[y]\) 在一个强联通分量中，存在x到y的路径，就存在y到x的路径 tarjan算法（非完全版） 标签：最小 完全 存在 tarjan算法 割点 size 优先 block for 原文地址：https://www.cnblogs.com/Z8875/p/13187415.html无向图
概念
时间戳
追溯值
割边判定法则
删除无向边\((x,y)\)后，图断开成两个部分隔点判定法则
若x是根节点，则x是割点当且仅当存在至少两个子节点\(y_1,y_2\)满足上条件有向图
有向图的强联通分量
代码
void tarjan(int x) {
dfn[x] = low[x] = ++dfcnt;
s[++top] = x;
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].t;
if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
else if (!b[y]) low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
cnt++;
while(1) {
int y = s[top--];
b[y] = cnt;
size[cnt]++;
if (x == y) break;
}
}
}