tarjan复健

02Ljh · 2023-11-12 14:46:17 · 算法·理论

2-SAT

区分 tarjan 解决三个连通性的东西时的变化。

强连通分量

只针对有向图的概念，即任意两点连通的极大子图。

在 tarjan 中要比无向图多考虑一个横叉边，即 dfs 时遇到一个原来访问过的边但不能形成强连通分量。

如蓝边为横叉边。

定义 low 为从 u 出发能到达的 dfn 序最小的点，但每次求完 SCC 相当于把该点删去来定义 low。

所以，我们维护一个队列表示可能能成为 SCC 的点，记录一个 ins 表示是否在访问队列里，如果更新的点被访问过且在队列中，就更新他的 low，否则证明该点已经成为强连通分量了，相当于把这个点删去了，不用更新。

更新 low 的时候因为定义可以写成 low[p]=min(low[p],low[i])。

void tarjan(int p)
{
    dfn[p]=low[p]=++ndf; q.pb(p); ins[p]=1;
    G(i,p)
    {
        if(!dfn[i]) 
        {
            tarjan(i);
            low[p]=min(low[p],low[i]);
        }
        else if(ins[i])
        {
            low[p]=min(low[i],low[p]);
        }
    }
    if(dfn[p]==low[p])//now is the lead of SCC from q.back()->p
    return ;
}

点双连通分量

无向图中只有返祖边，没有回边。low 的定义变为回溯后到达的最小的点编号。

先找割点，找到后如果 dfn_p \leq low_i，即 p 的儿子 i 再怎么回溯也不可能到达他上面的点，那么其为割点。（仅能通过走这个点使其联通）。当满足这个条件是，栈内的点即为点双。（q.back->p）

因为一个点可能被多个点双包含，所以不能把当前点出队，同时也要在遍历儿子的时候记录点双。

边双连通分量

显然每条边仅属于一个边双中。

先求出割边，然后把这条边标记为不能走，然后 dfs 即可。tarjan 找割边，low 的定义与点双相同，注意判断是否割边的时候与点双不同，如果 dfn_p=low_i，它不是割边但是是割点。