这是摘自算法书上的一篇 Tarjan 求割点算法
dfn[i] 代表时间戳数组
back[i] 代表该点 不依靠祖先节点 能回到的最远的祖先节点
采用链式前向星建图，结果存储在 iscut[ ] 数组中
点击查看代码
int head[N], cnt = 0;
struct Edge{
int from, to, nxt;
}e[N << 1];
void add(int u, int v){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[N], back[N], tim; // dfn[i] 时间戳 back[i] 回退到祖先
bool iscut[N]; // 结果数组
void dfs(int u, int fa){
dfn[u] = back[u] = ++tim;
int child = 0;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
// v 没访问过
child++;
dfs(v, u);
back[u] = min(back[u], back[v]);
if(back[v] >= dfn[u] && u != 1)
iscut[u] = true;
}
else if(dfn[v] < dfn[u] && v != fa){
back[u] = min(back[u], dfn[v]); // 注意不是 back[v]
}
}
if(u == 1 && child >= 2){
iscut[u] = true;
}
}
后来敲的时候，有一行代码为 back[u] = min(back[u], dfn[v]);容易误写为back[u] = min(back[u], back[v]
此时就要重视 back[ ] 表示 不依靠祖先节点
当然，这个稍微改动下，就是割边
点击查看代码
int head[N], cnt = 0;
struct Edge{
int from, to, nxt;
}e[N << 1];
void add(int u, int v){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[N], back[N], tim; // dfs[i] 时间戳 back[i] 回退到祖先
bool iscut[N << 1]; // 结果数组
void dfs(int u, int fa){
dfn[u] = back[u] = ++tim;
int child = 0;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
// v 没访问过
child++;
dfs(v, u);
back[u] = min(back[u], back[v]);
if(back[v] > dfn[u] && u != 1)
iscut[i] = true; // 边为
}
else if(dfn[v] < dfn[u] && v != fa){
back[u] = min(back[u], dfn[v]); // 注意不是 back[v]
}
}
if(u == 1 && child >= 2){
for(int i = head[u]; i != 0; i = e[i].nxt){
iscut[i] = true;
}
}
}
至于这份割边代码，iscut数组记录的倒是有些奇怪，但也能输出边的信息
标签：图论,割边,int,back,割点,dfn,&&,iscut From： https://www.cnblogs.com/9102qyy/p/18183165