无向图的割点

在无向图中，所有能互通的点组成了一个“连通分量”。
在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或多个，这种点称为割点(Cut vertex)。
在一个连通分量中，如果删除一个边，把这个连通分量分成了两个，
这个边称为割边(Cut edge)。

思考一个基本问题：在一个无向连通图G中有多少个割点？

一种暴力方法是：删除每个点，然后用DFS求连通性，
如果连通分量变多，那么就是割点。其复杂度为O(V(V+E))，不是好算法。
下面用DFS，即利用“深搜优先生成树”求割点。

在一个连通分量G中，对任意一个点s做DFS，能访问到所有点，
产生一棵“深度优先生成树”T。有以下定理：
定理1：T的根节点s是割点，当且仅当s有两个或更多的子结点。
定理2：T的非根结点u是割点，当且仅当u存在一个子结点v，
v及其后代都没有回退边连回u的祖先。
编程实现以上定理：设u的一个直接后代是v，
定义num[u]记录DFS对每个点的访问顺序，
num值随着递推深度增大而变大；
定义low[v]记录v和v的后代能连回到的祖先的num，
只要low[v]>=num[u]就说明在v这个支路上没有回退边连回u的祖先，最多退到u本身。

low：用于存储每个节点在DFS过程中能够回溯到的最早的节点的编号。
num：用于存储每个节点被访问的顺序编号。
dfn：用于记录当前的访问顺序编号。
iscut：一个布尔数组，用于标记是否为割点。

//代码实现
const int N = 109;
int low[N], num[N], dfn; // dfn记录递归的顺序，用于给num赋值
bool iscut[N];
vector<int> G[N]; // 存图
void dfs(int u, int fa)
{
    low[u] = num[u] = ++dfn;              // 初始值
    int child = 0;                        // 孩子数目
    for (int i = 0; i < G[u].size(); i++) // 处理u的所有子结点
    {
        int v = G[u][v];
        if (!num[v]) // v没被访问过
        {
            child++;
            dfs(v, u);
            low[u] = min(low[v], low[u]); // 用后代的返回值更新low值
            if (low[v] >= num[u] && u != 1)
                iscut[u] = true; // 标记割点
        }
        else if (num[v] < num[u] && v != fa)
            // 处理回退边，注意这里v!=fa，fa是u的父节点
            // fa也是u的邻居，但前面已经访问过，不需处理
            low[u] = min(low[u], num[v]);
    }
    if (u == 1 && child >= 2) // 根结点，有两个以上不相连的子树
        iscut[1] = true;
}
int main()
{
    int ans, n;
    // 输入图
​
    memset(low, 0, sizeof(low));
    memset(num, 0, sizeof(num));
    dfn = 0;
    memset(iscut, false, sizeof(iscut));
    ans = 0;
    dfs(1, -1);
    for (int i = 1; i <= n; i++)
        ans += iscut[i];
    printf("%d\n", ans);
}