割点

什么是割点

在无向图中所有能够互通的点构成了连通分量，其中有一些关键的点，如果删除它，如果这个联通分量被分成了两个或者更多，则称这个点为割点。

通俗的讲，现在有很多个主机连在一起构成网络，但是如果有一个主机烂掉了,你就无法访问洛谷，则称则称这个主机是一个割点。

求割点

在通过 DFS 遍历个图的时候，很容易发现如果一个点是割点，则它的儿子们都无法不通过还没被访问过的边返回割点之前的点，如下图所示：

可以发现节点 2、3 都是割点，节点 2 的子节点们不能在不通过节点 2 的情况下到达节点一，节点 3 的子节点们只能通过 3 到达节点 1、2。

但是节点 4 不是割点，因为节点 5 可以直接跳过节点 4 到达节点 3。

知道了求割点的原理之后我们考虑算法实现，定义两个数组 $dfn[i]$ 和 $low[i]$。

$dfn[i]$ 表示第 $i$ 个节点第一次被访问到的顺序。

$low[i]$ 表示第 $i$ 个节点和 $i$ 的后代在不经过已经被访问过的边的条件下，能到达的 $dfn[]$ 最小的节点。

将刚刚的图从节点 1 开始遍历得到的结果如下：

节点 4、5 都能通过一条另外的边返回节点 3。

故我们就有了以下的代码：

vector<int> G[maxn];
int dfn[maxn], low[maxn];
bool iscut[maxn];
int cutsum = 0;
int root;

void dfs(int x) {
    dfn[x] = low[x] = dfn[0]++;
    int son = 0;
    for(auto to : G[x]) {
        if(!dfn[to]) {
            son++;
            dfs(to);
            low[x] = min(low[x], low[to]);                      //如果他的后代能到达，那它也可以 
            if(low[to] >= dfn[x] && x != root) cutsum += !iscut[x], iscut[x] = true; /这样子写可以方便去重 
        }
        else    //如果边已经被访问过了，回退处理                                               
            low[x] = min(low[x], dfn[to]);
    }
    if(son >= 2 && x == root) cutsum += !iscut[x], iscut[x] = true;
}