算法复键——圆方树

干什么的把点双变成一个点怎么实现https://blog.csdn.net/zhangtingxiqwq/article/details/132645934代码总览voiddfs(intx){dfn[x]low[x]tot;z.push(x);for(inty:T[x]){if(!dfn[y]){dfs(y);low[x]min(low[x],low[y]);if(low[y]dfn[x]){cun(x,num);while(z.top()!y)cun(z.top(),num),z.pop();cun(y,num);z.pop();}}elselow[x]min(low[x],dfn[y]);}}不用记录父亲因为普通一条边也可以作为边双的一部分由于求的是边双而不是点双所以判断应为 low[y]dfn[x]表示y yy最多可以返祖到x xx关键解释dfn[x]low[x]tot;z.push(x);tot时间戳自增给 x 分配唯一访问序号dfn[x] low[x]刚搜到 x目前它能回退到的最小时间戳就是自己z.push(x)把 x 压入栈后续用来提取一整个点双连通分量。if(!dfn[y]){分支 1y 没访问过是子树节点向下递归。dfs(y);low[x]min(low[x],low[y]);递归搜儿子 y搜完回来再更新 x 的 low。子树 y 能绕回更小的时间戳x 也能走这条路更新 low[x]。if(low[y]dfn[x]){从 y 往下走最多只能绕回 x说明 x 是割点x–y 这条分支构成一个独立点双连通分量。此时要新建一个方点把栈里属于这个点双的所有圆点和方点连边。cun(x,num);while(z.top()!y)cun(z.top(),num),z.pop();cun(y,num);z.pop();num方点编号1生成新虚拟方点循环弹栈只要栈顶不是 y说明栈顶圆点都属于当前这个点双。到此一整个点双对应的圆方树的一个方点全部建完。}elselow[x]min(low[x],dfn[y]);分支2y 已经访问过回边不是父亲直接用 y 的时间戳dfn[y]更新 low[x]代表 x 能通过回边绕到更早的点。