(\%\%\%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;(叶子节点指只有一条边与该点相邻的点)。