强连通分量
细节
对于多点跑tarjan来说,可能会有先访问\(u\to v\)中的\(v\),这导致\(dfn[v]<dfn[x]\),后面\(x\)跑tarjan时会误把\(v\)当成祖先,要加判断
割点 & 割边
删去后使图不连通的点/边
找割边和强连通分量求法大差不差,这里不再赘述
找割点不同于前两者,首先割点不是low[x]==dfn[x]
的点,而是存在树边连接的儿子low[v]>=dfn[x]
的点,其次树根要特判
无向图连通分量
定义
边双:对于一个边双连通图,图上任意两点都有至少两条边不相交的道路(包括孤立点)
点双:对于一个点双连通图,图上任意两点都有至少两条点不相交的道路(包括孤立点)
其实这两种唯一的差别在于点双包含一种特殊情况——“杠铃形”子图,即两点有且仅有一条边相连,且该边为割边
由此引出另一个弱化的定义:
边双:不存在割边的连通图(包括孤立点)
点双:不存在割点的连通图(包括孤立点和“杠铃形”)
发现后面两个定义更易实现
细节
两者的实现有差别
边双更好理解,因为把所有割边去掉就得到所有边双,于是在tarjan找割边时顺便退出即可
点双不太一样,利用了点双的一些性质:
1、所有边在且仅在一个点双上;
2、两个点双间一定以割点分隔;
考虑在割点处进行统计,在判low[v]>=dfn[x]
后即可弹栈获取v所在点双,注意不要把割点给弹了
还有一件事:点双弹栈是以v为分界点的,不是x,栈内x,v之间可能有别的儿子
代码
边双:
void tarjan(int x,int pre) {
dfn[x]=low[x]=++index;
st[++stpos]=x;
erg(x,i) {
int v=e[i].to;
if(i==(pre^1)) continue;
if(!dfn[v]) {
tarjan(v,i);
low[x]=min(low[x],low[v]);
}
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]) {
stot++;
while(st[stpos+1]!=x) scc[stot].push_back(st[stpos--]);
}
}
点双:
void tarjan(int x,int pre) {
dfn[x]=low[x]=++index;
st[++stpos]=x;
int son=0;
erg(x,i) {
int v=e[i].to;
if(i==(pre^1)) continue;
if(!dfn[v]) {
tarjan(v,i);
low[x]=min(low[x],low[v]);
++son;
if(low[v]>=dfn[x]) {
++stot;
while(st[stpos+1]!=v) //注意边界
scc[stot].push_back(st[stpos--]);
scc[stot].push_back(x);
}
}
else low[x]=min(low[x],dfn[v]);
}
if(rt==x&&!son) { //特判孤立点
scc[++stot].push_back(st[stpos]);
}
}
标签:tarjan,++,int,stpos,算法,dfn,low
From: https://www.cnblogs.com/zhone-lb/p/18522205