P3388 Solution

SrsgPrince_ · 2023-05-12 23:50:36 · 题解

P3388 【模板】割点（割顶）题解

题目传送门：P3388 【模板】割点（割顶）。

这道题是 Tarjan 的模板题，Tarjan 的用处很多，能解决强连通分量，双连通分量，割点与桥。在这题里，我们用 Tarjan 来求割点。虽然 Tarjan 的代码看上去比较简短，但是它的思维比较复杂（类似于树状数组的思维难度，甚至还多）。

首先来看题的要求：“给定无向图，求割点”。那么先来讲一下什么是无向图：图中的每条边都是无方向的，则称这个图为 无向图，这点非常简单。最重要的是割点。

如果从图中删除这个顶点以及其相关的边之后，图不再连通（即分为两个及以上不相连的子图），那么这个顶点就是图的割点。如果一张图没有割点，那么就称这张图为 点双连通图，极大点双连通子图就被称为 点双连通分量。

按照 DFS 经过的边生成的树叫做 DFS 树，树上的边称为树边，其余的边称为 非树边。

非树边里又有 前向边、后向边 和 横叉边。

前向边：DFS 树上祖先指向子孙的边。
后向边：DFS 树上子孙指向祖先的边。
横叉边：非树边中不是前向和后向的边。即两颗不同子树的没有祖孙关系的点连的边。

这个给出一张图，能够从割点的定义看出割点为 1 和 5。

那么除了这种方法，还能怎么判定它呢，那么很自然地想到了 DFS（大法师）。首先，假设我们 DFS 从 u 访问到了 v，那么 u 就是 v 的父顶点，反过来 v 就是 u 的孩子顶点。在访问 u 前被访问过的，就是 u 的祖先顶点。

如果顶点 u 的所有孩子顶点可以不通过顶点 u 访问到 u 的祖先节点，那么此时去掉 u 就不影响整张图的连通性，那么 u 就不是割点。还是例如上图，用顶点 2 和 3 举例，顶点 2 的祖先顶点是顶点 1，从顶点 3 走，不一定要走 3-2-1，也可以是 3-4-1，于是去掉顶点 2，不影响整张图的连通，便有顶点 2 不是割点。相反的，如果顶点 u 存在一个孩子顶点，必须通过父节点 u 才能访问到 u 的祖先节点，那么去掉点 u 后，整张图不连通，那么 u 是一个割点。这次我们拿顶点 4 和 1 举例，顶点 1 的父顶点是顶点 5，从顶点 4 到 5，必定要经过顶点 1，并且删掉顶点 1 后，整张图不连通，那么顶点 1 是一个割点。

原理搞懂之后，我们来看实现过程，我们需要开两个新数组 dfn 和 low。这两个数组分别表示 DFS 访问到的顺序（也叫时间戳）以及经过至多一条非树边能到达的节点中最小的 DFS 序。因为在无向图里没有横叉边，而前向边对 low 值没有影响，所以我们只用判反向边。

那么我们把上面的原理再表示一下。

当对于某个顶点 u，如果存在至少一个顶点 v（u 的儿子），使得 low_v \geq dfn_u，即不能回到祖先，那么 u 点为割点。那么怎么更新这个 low 数组呢。首先在初始化的时候，我们先把每一个节点的 low 值赋为其 dfn 值，在后面的 DFS 中在进行更新。假设从顶点 u 到 v。当顶点 v 回溯到顶点 u 的时候，如果发现 dfn_v < low_u，那么 low_u = dfn_v。那么这样 low_u 就能表示经过至多一条非树边能到达的节点中最小的 DFS 序了。

换一张图，拿这张举例吧。先 DFS 一遍，节点编号就是 dfn 的值。接下来根据上面的思路来求出 low 值。得到下面这张图。

根据顶点 u，使得 low_v \geq dfn_u，那么 u 点为割点。我们能得到顶点 3，4 和 6 这三个点是割点，根据定义来看，都没问题。

对于这题来说，统计每一个点属于的点双连通分量的数量，如果一个点属于多个点双连通分量，那么它就是一个割点。

然后介绍一种常用的存图方式：链式前向星。

链式前向星与邻接矩阵和邻接表一样，也是主流的一种存图方式。它的整体结构很像邻接表，但是邻接表是线性结构，链式前向星是链式结构，实现方式不同，但是思想是一致的。

我们要用三个新的数组：

当新加入一条边 b-e 时：

++cnt 表示这条边的编号。
nxt[++cnt] = head[b] 表示原来以 b 作为起点的第一条边，作为该边的后续边。
des[cnt] = e 表示当前边的终点设置。

代码如下：

inline void addEdge(int b, int e) {
    nxt[++cnt] = head[b];
    des[head[b] = cnt] = e; // 这里把 head[b] = cnt 和 des[cnt] = e 放在了一起，底下一样
    nxt[++cnt] = head[e];
    des[head[e] = cnt] = b;
}

遍历方法就是从 head_u 开始找，一直找到末尾。

for (int i = head[u]; i; i = nxt[i]) {
    int v = des[i];
    // ......
}

删除一条边 u-vv 的做法：

int last=0;
for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v == vv) {
        if (i == head[u]) head[u] = nxt[i];
        else nxt[last] = nxt[i];
        break;
    }
    last = i;
}

那么我们可以通过之前的过程得出以下代码。

int head[maxn], nxt[maxn<<1], des[maxn<<1], cnt = 1;
inline void addEdge(int b, int e) {
    nxt[++cnt] = head[b];
    des[head[b] = cnt] = e;
    nxt[++cnt] = head[e];
    des[head[e] = cnt] = b;
}
// 链式前向星加边
int dfn[maxn], low[maxn], st[maxn], top;
int tot, deg[maxn], ind;
vector<int> vdcc[maxn]; // 存储点双连通分量
inline void tarjan(int u, int lst) {
    low[u] = dfn[u] = ++tot;
    st[++top] = u; // 压进栈内
    for (int i = head[u]; i; i = nxt[i]) {
        if (i != (lst ^ 1)) {
            int v = des[i], vv;
            if (!dfn[v]) { // 如果没有被访问过
                tarjan(v, i);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u]) { // 找到了新的割点
                    ++ind;
                    vdcc[ind].push_back(u);
                    ++deg[u];
                    // 加入深度最浅的点
                    do {
                        vv = st[top--];
                        vdcc[ind].push_back(vv);
                        ++deg[vv];
                    } while (vv != v);
                }
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
}

P3388 Solution

P3388 【模板】割点（割顶） 题解

P3388 【模板】割点（割顶）题解