今天考试因为不会敲 Dcc 的板子导致没有AK(还不是你太菜了)，所以特地写一篇博客记录 Tarjan 的各种算法
无向图的割点与桥
(各种定义跳过)
割边判定法则
无向边 (x,y) 是桥，当且仅当搜索树上存在 x 的一个子节点 y ,满足：
dfn[x]<low[y]
根据定义， dfn[x]<low[y] 说明从 subtree(y) 出发，在不经过 (x,y) 的前提下，不管走哪条边，都无法到达 x 或比 x 更早访问的节点。若把 (x,y) 删除，则 subtree(y) 就好像一个封闭的环境，与节点 x 之间没有 边相连，图断开成了两部分。因此 (x.y) 是割边。
下面的程序记录求出一张无向图中所有的桥。特别需要注意，通过边 xor 1 来判断是否通过一条无向边访问到了父节点。
int head[N];
int tot,sum;
int n,m,cnt=;
bool bridge[N];
int dfn[N],low[N]; struct Edge{
int to,nxt;
}edge[M]; void tarjan(int now,int in_edge){
dfn[now]=low[now]=++sum;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to,i);
low[now]=std::min(low[now],low[to]);
if(low[to]>dfn[now])
bridge[i]=bridge[i^]=;
}
else if((i^)!=in_edge) low[now]=std::min(low[now],dfn[to]);//记得加括号
}
}
割边
割点判定法则
若 x 不是搜索树的根节点，则 x 是割点当且仅当搜索树上存在一个 x 的子节点 y ，满足：
dfn[x]≤low[y]
特别地，若 x 是搜索树的根节点，则 x 是割点当且仅当搜索树上存在至少两个子节点 y1,y2 满足上述条件。
下面的程序求出一张无向图中所有的割点。因为割点判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从 x 出发能访问到的所有节点的时间戳都可以用来更新 low[x]。
int root,n,m;
bool is_cut[N];
int stk[N],top;
int cnt,tot,sum;
int dfn[N],low[N]; struct Edge{
int to,nxt;
}edge[M]; void tarjan(int now){
dfn[now]=low[now]=++sum;
int flag=;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to);
low[now]=std::min(low[now],low[to]);
if(low[to]>=dfn[now]){
flag++;
if(now!=root||flag>) cut[now]=;
}
}
else low[now]=std::min(low[now],dfn[to]);
}
}
割点
无向图的双联通分量
定理
一张无向连通图是“点双联通图”，当且仅当满足下列两个条件之一：
- 图的顶点数不超过2。
- 图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环，也就是我们通常画出的环。
一张无向连通图是“边双联通图”，当且仅当任意一条边都包含在至少一个简单环中。
边双联通分量(e-DCC)的求法
边双联通分量的计算非常容易。只需求出无向图中所有的桥，把桥都删除后，无向图会分成若干个联通块，每一个联通块就是一个“边双联通分量”。
在具体的程序实现中，一般先用 Tarjan 算法标记出所有的桥边。然后，再对整个无向图执行一次深度优先遍历(遍历的过程不访问桥边)，划分出每个联通块。下面代码在 Tarjan 求桥的参考程序基础上，计算出数组 c ，c[x] 表示节点 x 所属的“边双联通分量”的编号。
int c[N],dcc;
void dfs(int now){
c[now]=dcc;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(c[to]||bridge[i]) continue;
dfs(to);
}
}
//以下代码片段加在 main 函数中
for(int i=;i<=n;i++){
if(!c[i]) ++dcc,dfs(i);
}
e-DCC
e-DCC的缩点
把每个 e-DCC 看做一个节点，把桥边 (x,y) 看作连接编号为 c[x] 和 c[y] 的无向边，会产生一棵树(若原图不连通，则产生森林)。这种把 e-DCC 收缩为一个节点的方法就称为“缩点”。下面的代码在 Tarjan 求桥、求 e-DCC 的参考程序基础上，把 e-DCC 缩点，构成一棵新的树(或森林)，存储在另一个邻接表中。
int rcnt=;
int rhead[N]; struct Redge{
int to,nxt;
}redge[M]; void add_c(int x,int y){
redge[++rcnt].to=y;
redge[rcnt].nxt=rhead[x];
rhead[x]=rcnt;
} //以下代码片段加在 main 函数中
for(int i=;i<=cnt;i++){
int x=edge[i].to;
int y=edge[i^].to;
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
add_c(c[y],c[x]);
}
e-DCC缩点
点双联通分量(v-DCC)的求法
若某个节点为孤立点，则它自己单独构成一个 v-DCC。除了孤立点之外，点双联通分量的大小至少是 2。根据 v-DCC 定义中的“极大”性，虽然桥不属于任何 e-DCC，但是割点有可能属于多个 v-DCC。
为了求出“点双联通分量”，需要在 Tarjan 算法的过程中维护一个栈，并按照如下方法维护栈中的元素：
1.当一个节点第一次被访问时，把该节点入栈。
2.当个点判定法则中的条件 dfn[x]≤low[y] 成立时，无论 x 是否为根，都要：
(1) 从栈顶不断弹出节点，直至节点 y 被弹出。
(2) 刚才弹出的所有节点与节点 x 一起构成一个 v-DCC。
下面的程序在求出割点的同时，计算出 vector 数组 dcc，dcc[i] 保存编号为 i 的 v-DCC 中的所有节点。
void tarjan(int now){
stk[++top]=now;
dfn[now]=low[now]=++tot;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]) {
tarjan(to),low[now]=min(low[now],low[to]);
if(low[to]>=dfn[now]) {
sum++;
do{
z=stk[top--];
}while(z!=to);
}
} else low[now]=min(low[now],dfn[to]);
}
}