\(\%\%\%tarjan\)
有向图
强联通分量
DAG 的一些结论
- 图中唯一出度为0的点，将会受到所有点的%%
- 给所有入度为0的点传消息，那么消息会传到所有点（这也是传给初始点最少的方案）
- 使DAG上任意一点都被至少一个环覆盖，至少要添边 \(max\){入度为\(0\)的点的个数，出度为\(0\)的点的个数}
P.S.:
- 别忘了DAG中的一个点对应原图中的一个强联通分量(答案要输出强联通分量中的点)。
无向图
割点和点双
-
因为点双联通分量的求法与众不同(别的都是自己求自己，而点双是父亲求儿子)，这就导致了 \(father\) 割掉 \(child\) 时还有别的 \(child\) 在 \(stack\) 内，
所以只能出栈到 \(child\)( \(child\) 未出栈)，然后手动加上 \(now\) 和 \(child\) (即 \(v\)).
-
\(root\) 与他的每一个 \(child\) (确切的说是与 \(child\) 在 \(stack\) 内的结点) 构成点双。
证明：\(v\) 的 \(child\) 中 \(low[child]<=dfn[v]\) 的已经出栈了，剩余的 \(v's \space childs\) ,必然有 \(low[v \space childs]==dfn[root]\)
因为\(low[v's \space childs]\)
既不可能 \(<dfn[root]\) ,也不可能指向其他子树。故必有后向边指向\(root\),即证。
-
一个点可能同时属于多个点双（割点），若用染色法标记点双，请用数组套 \(vector\) 或 数组套 \(set\) .
求割点的Code：
int dfn[N],low[N],times=0;
set<int> cut;
void tarjan(int now,const int &fa)
{
dfn[now]=low[now]=++times;
rint i,v,child=0;
for(i=one[now];i>0;i=Next[i]) {
v=ver[i];
if(!dfn[v]) {
child++;
tarjan(v,now);
if((fa==0&&child>1)||(fa!=0&&low[v]>=dfn[now]))
cut.insert(now);
low[now]=min(low[now],low[v]);
}
else //if(v!=fa) // 割点并不需要这句，但是指向father的low确实没有意义。（指向father的祖先才有意义）。 但桥要。
low[now]=min(low[now],dfn[v]);
}
return;
}
（也可以开一个\(bool\) 数组来标记）
求点双的代码：
int dfn[N],low[N],times=0;
set<int> col[N];
int all=0;
int S[N],top=0;
int siz[N];
void tarjan(int now,const int &fa)
{
dfn[now]=low[now]=++times;
top++,S[top]=now;
rint i,v,child=0;
for(i=one[now];i>0;i=Next[i]) {
v=ver[i];
if(!dfn[v]) {
child++;
tarjan(v,now);
if((fa==-1)||(fa!=-1&&low[v]>=dfn[now])) {
all++;
while(S[top]!=v) {
siz[all]++;
col[S[top]].insert(all);
S[top]=0; top--;
}
col[v].insert(all); S[top]=0,top--;
col[now].insert(all);
siz[all]++; siz[all]++;
}
low[now]=min(low[now],low[v]);
}
else low[now]=min(low[now],dfn[v]);
}
return;
}
不得不说一下 \(STL\) 栈和手写栈的优缺点了
- STL \(stack\) 能减少码量，动态空间，但不方便调试。
- 手写栈方便调试，但会多上几行。
关于点双的一些结论
-
如果一个点双联通分量的 \(size>=2\) ，则点双中任意两点 \(u\),\(v\)，必然存在至少两条 互不重叠（指路径上除了起点和终点外，没有相同的点）的路径，
而对于点双中的一点\(u\)和不在此点双中的一点\(v\),则不会存在两条路径互不重叠。
证明：
先证 点双（size>2）中任意两点 必然存在至少两条 互不重叠的路径，：
若只存在一条，那么去掉其中一点（不是任意，是连着其他点的点），不联通，违反了定义，即证。
再证
而对于点双中的一点\(u\)和不在此点双中的一点\(v\),则不会存在两条路径互不重叠。
若存在，则 \(v\) 也在此点双中，违反了定义，即证。
一定要记得特判 size
桥和边双
一些结论
- 一个点只能属于一个边双联通分量
- 把一个无向无环图（通过加边）变成使每一个点都至少在一个环上的代价是
(叶子节点数+1)>>1;(叶子节点指只有一条边与该点相邻的点)。