【图论】割边与割点

Tue Jun 27 2023

7 分钟

技术 OI学习笔记图论 Tarjan 图论 OI cpp 割点割边连通分量无向图

1400 字

概念#

在无向图中，割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。割点与割边的关系

有割点不一定有割边，有割边一定有割点。
割边的两个端点中一定有一个是割点。

求解思路#

割点与割边的求解都使用Tarjan算法实现

求割边#

求解割边的方法与求解有向图中的强连通分量十分相似，我们可以在原有基础上修改。为什么这样说呢？

理论前提#

我们回顾一下割边的定义，如果去掉这条边，这个图变成了不连通的两个独立的部分。这说明这两部分之间只通过这一条边连接，反过来说就是有两条边连接的两个部分中不存在割边。这就与我们有向图中的强连通分量很像了，我们也可以通过 DFS 树+顶点表示法来表示一个割边。

虽然这是一幅无向图，但实际上在 DFS 的过程中就已经有了 DFS 序，我们也与有向图的 DFS 树一样有树边与非树边的区别。那么我们现在所有的形式其实与求解强连通分量一样了：给每个结点打上它的 DFS 序和可以回到的结点序，如果两个不一样，说明它与它能回到的结点之间有两条通路连接——说明它们两个之间的边都不可能是割边，因为树边已经连接了里面的所有点，加上这一条非树边，那么每个点到其他点都有了两条通路，不管割掉那一条边都不管用。

算法实现#

因为是无向边，我们还要注意一个小问题——重边。不同于有向图中的重边，这个重边是会实实在在影响到我们的。比如原来两个点只有一条边相连，这样一条边显然是一条割边。但如果是重边呢？那它就不是割边了，我们需要特判这种情况，有两个选择：

使用 vector，给每一条边加上 id 值，注意添加无向边时两个有向边的结点是相同的，因为它们本质上是一条无向边：
CPP
```
1
2
```
```
vector<vector<pair<int, int>>> g(N); // 建图
for(auto i : g[j]); // 遍历
```
换用链式前向星，因为链式前向星自带 id，不用多占空间速度还快，是很好的选择。不过由于一条无向边使用两条有向边”聚合”而成，我们先把边数 tot 赋值为 1，这样只需要通过按位异或就可以判断其属于哪一个结点了：
CPP
```
1
```
```
int tot = 1; // 注意赋值为一
```

struct node { int ver; int nxt; }edge[N * 2];

void add(int u, int v) { edge[++tot].ver = v; edge[tot].nxt = head[u]; head[u] = tot; }

//示例，判断 id 为 a 和 b 的结点是不是同一条无向边 if(a == (b ^ 1))…

PLAINTEXT


下面就好办了，与求解强连通分量一样的写法。不过注意我们可以优化一个小地方，在溯回的时候我们可以直接判断``if(up[y] > dfn[x])``如果是真的就代表下面的结点回不到x结点——也就是说x结点与y结点之间隔了一条割边，我们直接添加它就可以了：

```cpp
namespace e_DCC
{
    vector<int> dcc;
    int dfn[N], up[N], crd = 0;

    void dfs(int x, int from)
    {
        dfn[x] = up[x] = ++crd;
        for(int i = head[x]; i; i = edge[i].nxt)
        {
            int y = edge[i].ver;
            if(!dfn[y])
            {
                dfs(y, i);
                up[x] = min(up[x], up[y]);
                if(up[y] > dfn[x])
                    dcc.push_back(i);
            }
            else if (i != (from ^ 1))
                up[x] = min(up[x], up[y]);
        }
    }
}

求割点#

不同之处#

求割点的方法与割边几乎一致，但请注意下面的情况：

首先我们很容易的发现如果按照原来的算法这个图啥也不是，因为每个点都可以回到出发点 1，可图上明明有 4、7 这两个割点啊！所以我们应该把原来的up[x] = min(up[x], up[y]);改成up[x] = min(up[x], dfn[y]);，防止结点通过多次跳跃割点回到上面。

而如果我们还是按照原来的判定if(up[y] > dfn[x])，就会发现当up[y] = dfn[x]时就漏情况了。所以我们再把缺失的等于号加上。

然而这还没有完，注意下面的情况，结点一完美满足我们的所有要求，可是它不是割点啊！因此我们还需要特判 DFS 进入的结点，只有当它的子节点数量大于等于二时才是割点，否则取消它的割点资格。

示例2

算法实现#

根据我们上面的推导，很容易通过 e_DCC 改出 v_DCC 的算法：

CPP

bool cut[N]; // 第i个结点是不是割点

namespace v_DCC
{
    int dfn[N], up[N], crd = 0;
    bool cut[N];

    void dfs(int x, int from)
    {
        dfn[x] = up[x] = ++crd; // init x
        int ch = 0;
        for(int i = head[x]; i; i = edge[i].nxt)
        {
            int y = edge[i].ver;
            if(!dfn[y]) // y not have
            {
                dfs(y, i); ch++;
                up[x] = min(up[x], up[y]);
                if(up[y] >= dfn[x]) cut[x] = true;
            }
            else if (i != (from ^ 1))
                up[x] = min(up[x], dfn[y]);
        }
        if(from == 0 && ch <= 1) cut[x] = false;
        ans += cut[x];
    }
}

【图论】割边与割点

https://frosti.saroprock.com/blog/割边与割点/