Connect

强连通分量¶

强连通分量即一个点集，集合中任意一对结点(u, v) 都互相可达

Tarjan算法¶

Tarjan算法输入为一张有向图，执行一次dfs，输出为多个点的集合，每个集合是一个强连通分量

具体方法为进行多次dfs，对每个节点记录两个值

dfn: 这个节点的编号，从1开始，访问到一个空白点即标记，并将序号加1
low: 这个点能访问到的节点的最小dfn值，一开始置为自身的dfn

tarjan(u) {
    DFN[u] = Low[u] = ++Index                      // 为节点u设定次序编号和Low初值
    Stack.push(u)                              // 将节点u压入栈中
    for each (u, v) in E                       // 枚举每一条边
        if (v is not visted)               // 如果节点v未被访问过
            tarjan(v)                  // 继续向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                   // 如果节点v还在栈内
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
        repeat
            v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
            print v
        until (u== v)
}

算法思想其实就在于计算每个点可以向前访问搜索子树中点，然后一直向前追溯，直到遇到一个点无法访问更前面的节点，那么从栈顶到这个节点的这些节点都可以互相访问，是一个强连通分量，没有仔细去思考证明，但大概思路可以这样想

设u的dfn和low相等，此时u上面还在栈内的有若干元素，那么从u开始，都可以访问到这些节点，因为是从u开始执行的dfs，而反过来，因为后面这些点都有指向前面的边，可以这些节点都可以访问到u，因此是强连通分量

割点和割边¶

割点和割边是对于无向图来说的

割点: 去掉这个点后，整张图连通分量个数增加
割边: 去掉这个边后，整张图连通分量个数增加

可以用Tarjan算法来求，和求强连通分量的Tarjan有所区别，不过整体流程类似

对每个节点，求两个值

dfn: dfs搜索到一个节点时的序号
low: 节点除过父节点外可以访问到的最小序号

算法思路可以这样想，对一个连通分量，一次dfs一定可以完全搜索完，在搜索过程中，逐个来看每个节点是不是割点，每条边是不是割边即可

这里判断删除一个点、一条边后连通分量是否增加，就看搜索过的部分和之后的部分会不会分开，即看孩子节点能否绕过父节点到达祖先节点

判断方法是

割点，这里要根绝是否是根节点进行区分
- 根节点: 看彼此无法连接的子节点是否多于一个，这里在外围进行计算，对根节点每个孩子开始遍历，如果孩子的low还没有设置，运行tarjan算法，并且根节点子树数量+1，最后看子树数量是否大于1
- 其它节点: low(v) <= dfn(u)
割边: low(v) < dfn(u)

这里low(v)=dfn(u)指存在以下情况，v1可以通过v2连接到u，那么删除u，同样可以分割，所以割点判断条件中加入相等；而对于割边，则不成立，因此割边必须是严格偏序关系

     u
   /   \
  v1 -- v2

例题