割点 | GZTime's Blog

图的割点

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

核心思想

给每一个点一个访问顺序称为 $order$
在 dfs 过程中如果访问到了割点 $k$ 则此时图会被 $k$ 分为 2 部分：已访问的点和未访问的点
在未访问的点中至少存在一个点满足在不经过 $k$ 的前提下再也回不到已经访问过的点
如果不是连通图，则需要遍历全部可能作为根的节点
```
[1]--[3]
 |    |
[4]--[2]--[6]
      |    |
     [5]--[7]
```

如上图，在访问过程中，以[1]为根节点则访问顺序为

node	1	2	3	4	5	6	7
order	1	3	4	2	7	5	6

这时候每个点在不经过其父节点的时候能到达的最早的点的访问顺序是

node	1	2	3	4	5	6	7
last	1	1	1	1	3	3	3

对于 2 号点

nodes[2].order == nodes[2].child.last

所以 2 号点是割点

示例代码

#include <bits/stdc++.h>
using namespace std;

struct Side
{
    int _node;
    int node_;
    int next;
};

struct Node
{
    vector<Side> sides;
    int order;
    int lastest;
    bool CutFlag;
};

vector<Node> nodes;
int n_node, n_side, orderIndex = 0, num = 0;

void getdata()
//存入无向图
{
    cin >> n_node >> n_side;
    Node no;
    no.order = 0;
    no.lastest = 0;
    no.CutFlag = false;
    vector<Node> tmp(n_node + 1, no);
    nodes = tmp;
    tmp.clear();
    for (int i = 0; i < n_side; i++)
    {
        Side s;
        cin >> s._node >> s.node_;
        s.next = s._node;
        nodes[s.node_].sides.push_back(s);
        s.next = s.node_;
        nodes[s._node].sides.push_back(s);
    }
}

void dfs(int now, int fa)
//核心程序
{
    orderIndex++;
    nodes[now].order = orderIndex;
    nodes[now].lastest = orderIndex;
    //一切之前每一个节点的序号和最前祖先都是自己
    int child = 0;
    for (unsigned int i = 0; i < nodes[now].sides.size(); i++)
    {
        int next = nodes[now].sides[i].next;
        //遍历邻接边
        if (nodes[next].order == 0)
        //没有访问过
        {
            child++;
            dfs(next, now);
            //搜索下一个
            nodes[now].lastest = min(nodes[now].lastest, nodes[next].lastest);
            //当前点的最前祖先是 min(当前祖先，下一个点的最前祖先)
            if ((now != fa && nodes[now].order <= nodes[next].lastest) || (now == fa && child > 1))
            //当前节点不是根节点时候如果你的序号小于你孩子的最高记录
            //当前节点是根节点时候当且仅当子树个数>2 时候拥有
            {
                if(!nodes[now].CutFlag) num++;//避免重复计算
                nodes[now].CutFlag = true;//更改标记
            }
        }
        else
            nodes[now].lastest = min(nodes[now].lastest, nodes[next].order);
            //对于已经访问过的"子节点"进行最小值选择
    }
    return;
}

int main()
{
    getdata();

    for(int i = 1; i <= n_node; i++)
        if(nodes[i].order == 0)
            dfs(i,i);

    cout << num << endl;
    for (int i = 0; i <= n_node; i++)
        if (nodes[i].CutFlag)
            cout << i << " ";

    cout << endl;
    for(int i = 1; i <= n_node; i++)
        cout << nodes[i].order << " ";

    cout << endl;
    for(int i = 1; i <= n_node; i++)
        cout << nodes[i].lastest << " ";
    return 0;
}