Tarjan [割点, 缩点, 桥(待填坑)]

• $割点$割点

删除这个点后, 图的联通块数量变多.

$DFS$DFS 时, 设当前点为 $k$k, $low\left[\right]$low[] 为最高祖先, $dfn\left[\right]$dfn[] 为 $dfs$dfs 序, $to$to 为 $k$k 直接相连的点,

• 若 $to$to 点被访问过, 则说明 $k$k 有向上的边, $low\left[k\right]=min\left(low\right[k],dfn[to\left]\right)$low[k]=min(low[k],dfn[to])

• 否则沿着 $to$to 继续递归, 回溯时 $low\left[k\right]=min\left(low\right[k],low[to\left]\right)$low[k]=min(low[k],low[to]),
  
  若 $low\left[to\right]$low[to] 在 $k$k 下方, 说明切掉 $k$k, $to$to 会在下方形成一个独立的环,

  1. 若 $k$k 不为根节点, $k$k 为 割点 ,
  2. 若 $k$k 为根节点, 必须有两个以上儿子才算是割点 .

void Tarjan(int k){
        low[k] = dfn[k] = ++ tim;
        int cnt = 0, siz = 0;
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(dfn[to]) low[k] = std::min(low[k], dfn[to]);
                else {
                        siz ++;
                        Tarjan(to);
                        low[k] = std::min(low[k], low[to]);
                        if(low[to] >= dfn[k]){
                                cnt ++;
                                if(k != root || cnt > 1) cut[k] = 1;
                        }
                }
        }
}

• $缩点\left(边双\right)$缩点(边双)

将边双联通分量缩点 .

$DFS$DFS 时, 定义同上, 每次将当前节点压入 栈 中,
当 $low\left[k\right]=dfn\left[k\right]$low[k]=dfn[k] 时, 说明 $k$k节点以下在 栈 中的元素共同构成一个 强联通分量,
此时弹出 栈 内元素, 得到新的环.
与上方判环的方式不同的是, 这里开了个 $in\_stk\left[\right]$in_stk[] 数组, 来判断是否在环内.

注意: 只有在栈中, 才能用来更新 $low$low

void Tarjan(int k){
        Dfn[k] = low[k] = ++ t_num;
        stk.push(k);
        in_stk[k] = 1;
        for(int i = head[k]; i; i = edge[i].next){
                int t = edge[i].to;
                if(!Dfn[t]) Tarjan(t), low[k] = std::min(low[k], low[t]);       //WRONG #1
                else if(in_stk[t]) low[k] = std::min(low[k], Dfn[t]);
        }
        if(Dfn[k] == low[k]){
                block[k] = ++ block_num;
                block_size[block_num] ++;
                while(stk.top() != k){
                        block[stk.top()] = block_num;
                        block_size[block_num] ++;
                        in_stk[stk.top()] = 0;
                        stk.pop();
                }
                in_stk[k] = 0;
                stk.pop();
        }
}

• $缩点\left(点双\right)$缩点(点双)

将点双联通分量缩点 .

$DFS$DFS 时, 设当前节点为 $k$k, 连向的节点为 $to$to,

• 若 $to$to 访问过且 $dfs$dfs序比 $k$k 小, 说明 $to$to 和 $k$k 为一个环的首尾, 将边 $k,to$k,to 加入栈中 .
• 若 $to$to 没有访问过, 先将边 $k,to$k,to 加入栈中, 递归处理 $to$to, 然后检查 $low\left[to\right]$low[to] 是否大于等于 $dfn\left[k\right]$dfn[k],
  若小于, 则不用管, 会在 $low\left[to\right]$low[to] 处通过弹栈操作处理掉 首 为 $low\left[to\right]$low[to] 的环,
  若大于等于, 说明 $to$to 可能在 $k$k 以下构成了环, 也可能与 $k$k 在同一个环内,
  • 对第一种情况, $k$k 和 $to$to 通过弹栈操作仍然能构成点双联通 .
  • 对第二种情况, $k$k 和 $to$to 在 $DFS$DFS $k$k 这层可以通过弹栈操作找出环 .

void Tarjan(int k, int fa){
        low[k] = dfn[k] = ++ tim; 
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(!dfn[to]){
                        stk.push(k), stk_2.push(to);
                        Tarjan(to, k), low[k] = std::min(low[k], low[to]);
                        if(low[to] < dfn[k]) continue ;
                        bk_cnt ++;
                        while(!stk.empty()){
                                int tp = stk.top(), tu = stk_2.top();
                                bk[bk_cnt].pb(tp), bk[bk_cnt].pb(tu);
                                stk.pop(), stk_2.pop();
                                if(tp == k && tu == to) break ;
                        }
                }else if(dfn[to] < dfn[k] && to != fa){
                        stk.push(k), stk_2.push(to);
                        low[k] = std::min(low[k], dfn[to]);
                }
        }
}

• $相关例题$相关例题

1. 例题1
2. 例题2
3. 例题3
4. 例题4