新人来了！
2026-08-17 19:55:43
发布于：浙江
其实已经不算新了~只不过之前*了几年，最近上小码王的NOIP冲刺班~
听说ACGO是一个学术网站，我看到最近有好多人被禁言了啊，那肯定是因为不够学术吧~
那我必须写一个学术帖了，说不定啥时候也会被封了还不知道呢？
讲什么呢？那就讲今天NOIP模拟赛的题吧~赛时不会这个知识点没拿到分TvT
那就开始吧！
点双连通分量
声明：洛谷在这题中说，
一种定义是“图中任意两不同点之间都有至少两条点不重复的路径”，而另外一种是“不存在割点的图”，这两种定义存在细微差别，具体体现在两个点之间有一条连边构成的图。
但是一般情况下我们讨论的都是长度>2或者有关割点的问题，所以这里也就采用第二种定义了~
首先回顾求割点的方法：递归，若 点dfs树儿子存在 ，则该点为割点。
还要注意特判一下dfs到的第一个点的情况，因为它没有父亲节点，好可怜qwq（不是），所有点对于它来说 一定是大的，但这并不能说明它是割点。只有当要dfs至少两次时它才是这几个dfs的块的割点。
那么点双连通分量应该怎么求呢？
我们可以用有向图强连通分量类似的方法，用栈维护强连通分量。
具体地，我们开一个栈，在递归到一个点 时，我们将它入栈。然后我们访问它的所有树儿子，如果发现这个点与树儿子 还是满足老套路 ，那么说明这个点是割点，与下面的节点形成一个点双联通分量。
但是这时，虽然树根可能不是割点，但它一定与下面的点构成一个点双连通分量，所以和上面的一样，不需要特判。（感觉更好写了？qwq）
这里直接偷洛谷第一篇题解的图嘿嘿，你们可以根据这张图自己理解一下OvO
我本来想写代码的，但是太懒了qwq，代码放 OIwiki 的吧：
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;
struct edge {
int to, nt;
} e[M << 1];
int hd[N], tot = 1;
void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }
void uadd(int u, int v) { add(u, v), add(v, u); }
int ans;
int dfn[N], low[N], bcc_cnt;
int sta[N], top, cnt;
bool cut[N];
vector<int> dcc[N];
int root;
void tarjan(int u) {
dfn[u] = low[u] = ++bcc_cnt, sta[++top] = u;
if (u == root && hd[u] == 0) {
dcc[++cnt].push_back(u);
return;
}
int f = 0;
for (int i = hd[u]; i; i = e[i].nt) {
int v = e[i].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (++f > 1 || u != root) cut[u] = true;
cnt++;
do dcc[cnt].push_back(sta[top--]);
while (sta[top + 1] != v);
dcc[cnt].push_back(u);
}
} else
low[u] = min(low[u], dfn[v]);
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m;
int u, v;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
if (u != v) uadd(u, v);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) root = i, tarjan(i);
cout << cnt << '\n';
for (int i = 1; i <= cnt; i++) {
cout << dcc[i].size() << ' ';
for (int j = 0; j < dcc[i].size(); j++) cout << dcc[i][j] << ' ';
cout << '\n';
}
return 0;
}
圆方树
求出所有点双联通分量后建每个分量对应的虚点（记为“方点”），虚点与所属点双的每个点（记为“圆点”）连边，会形成一棵树。然后这棵树就相当于点双连通分量缩点之后的树，但是很好地保留了原树的形态。
懒得找例题了，直接放模拟赛题的特殊性质 B吧：
给定一张 个点 条边的无向图，其中 个点被封锁，分别为 。被封锁的点可以到达，但是不可以走出。定义 代表额外封锁节点 后，从 开始可以到达的被封锁点的数量。对于 ，分别求出 的值。如果不存在，输出 。
听起来是不是很难？我当时也是这么想的，但是经过我苦苦思考两个小时，还是想出来了大概解法，我真厉害！
考虑先在图中删除所有 ，并对删除后的图跑个点双连通分量。根据定义，显然如果封锁的点在点双连通分量的内部，则不会影响，都能到达（除了一开始就被其他 堵住的）；否则被封锁的点一定是割点。
现在的问题转化成了，删除这个点后，有多少个 会被影响不能到达。
赛时的想法是，直接对点双缩点建树，大力分讨，但我毕竟是新手啊，不会写太长的代码ToT，而且当时也不会求点双连通分量，最后只能拿0分了，好悲惨。
我们考虑对这个图建一棵圆方树，则 被影响当且仅当这个点在原图中所有邻居在圆方树 的路径的公共点中，由于这是一棵树，所以显然是以 为根，所有邻居的LCA 的路径。
然后做个树上差分即可。
所以，有了圆方树，再难的问题，也能变简单！
说完了，下课！！！哈哈哈哈哈哈哈哈哈！
有帮助，赞一个