点双连通分量 & 圆方树
2026-08-24 19:46:39
发布于：广东
模拟赛被信息差了，正解想到了但不知道圆方树最终获得了暴力分遗憾离场，故记录于此。
小号保存的文章不考虑删除。
点双连通分量
声明：一种定义是“图中任意两不同点之间都有至少两条点不重复的路径”，而另外一种是“不存在割点的图”，这两种定义存在细微差别，具体体现在两个点之间有一条连边构成的图。但是一般情况下我们讨论的都是长度 或者有关割点的问题，所以采用第二种定义。
首先回顾求割点的方法：递归，若 点 dfs 树儿子存在 ，则该点为割点。
还要注意特判一下 dfs 到的第一个点的情况，因为它没有父亲节点，所有点对于它来说 一定是大的，但这并不能说明它是割点。只有当要 dfs 至少两次时它才是这几个 dfs 的块的割点。
那么点双连通分量应该怎么求呢？
我们可以用有向图强连通分量类似的方法，用栈维护强连通分量。
具体地，我们开一栈，在递归到一个点 时，我们将它入栈。然后我们访问它的所有树儿子，如果发现这个点与树儿子 满足 ，那么说明这个点是割点，与下面的节点形成一个点双联通分量。
但是这时，虽然树根可能不是割点，但它一定与下面的点构成一个点双连通分量，所以和上面的一样，不需要特判。
这里直接偷洛谷第一篇题解的图，根据图自己理解一下。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <std::vector <int>> v(n + 5);
for(int i = 1; i <= m; i++){
int x, y;
std::cin >> x >> y;
if(x == y) continue;
v[x].push_back(y);
v[y].push_back(x);
}
std::vector <int> low(n + 5), dfn(n + 5), stack;
std::vector <std::vector <int>> bcc;
int curdfn = 0, curbcc = 0, root = -1;
auto tarjan = [&](auto &&self, int cur) -> void{
low[cur] = dfn[cur] = (++curdfn);
stack.push_back(cur);
if(cur == root && v[cur].empty()){
bcc.push_back({cur});
return;
}
for(int i:v[cur]){
if(!dfn[i]){
self(self, i);
low[cur] = std::min(low[cur], low[i]);
if(low[i] >= dfn[cur]){
int tmp = stack.back();
bcc.push_back({});
do{
tmp = stack.back();
bcc[bcc.size() - 1].push_back(tmp);
stack.pop_back();
}while(tmp != i);
bcc[bcc.size() - 1].push_back(cur);
}
}else{
low[cur] = std::min(low[cur], dfn[i]);
}
}
};
for(int i = 1; i <= n; i++){
if(!dfn[i]) root = i, tarjan(tarjan, i);
}
std::cout << bcc.size() << '\n';
for(auto it:bcc){
std::cout << it.size() << ' ';
for(int j:it) std::cout << j << ' ';
std::cout << '\n';
}
}
}
时间复杂度：。
诶等等，这是不是叫 dcc 来着，变量名写错了（（（
圆方树
这为啥是紫的？但是水紫它不香吗（
求出所有点双联通分量后建每个分量对应的虚点（记为“方点”），虚点与所属点双的每个点（记为“圆点”）连边，会形成一棵树。然后这棵树就相当于点双连通分量缩点之后的树，但是很好地保留了原树的形态。
例题（模拟赛题，特殊性质 B）：
给定一张 个点 条边的无向图，其中 个点被封锁，分别为 。被封锁的点可以到达，但是不可以走出。定义 代表额外封锁节点 后，从 开始可以到达的被封锁点的数量。对于 ，分别求出 的值。如果不存在，输出 。
考虑先在图中删除所有 ，并对删除后的图跑个点双连通分量。根据定义，显然如果封锁的点在点双连通分量的内部，则不会影响，都能到达（除了一开始就被其他 堵住的）；否则被封锁的点一定是割点。
现在的问题转化成了，删除这个点后，有多少个 会被影响不能到达。
赛时的想法是，直接对点双缩点建树，大力分讨，但码量过于巨大。
我们考虑对这个图建一棵圆方树，则 被影响当且仅当这个点在原图中所有邻居在圆方树 的路径的公共点中，由于这是一棵树，所以显然是以 为根，所有邻居的 LCA 的路径。
然后做个树上差分即可。
namespace cjdst{
const int N = 2000000, M = 20;
pii edge[N + 5];
std::vector <int> v[N + 5], v2[N + 5];
int a[N + 5];
bool flag[N + 5];
int ans[N + 5];
int n, m, siza, ctnode;
int firstans;
int low[N + 5], dfn[N + 5];
int father[N + 5][M + 1], dep[N + 5];
int tr[N + 5];
std::vector <int> stack;
int curdfn;
void tarjan(int cur){
low[cur] = dfn[cur] = (++curdfn);
stack.push_back(cur);
for(int i:v[cur]){
if(flag[i]) continue;
if(dfn[i]){
low[cur] = std::min(low[cur], dfn[i]);
continue;
}
tarjan(i);
low[cur] = std::min(low[cur], low[i]);
if(low[i] < dfn[cur]) continue;
ctnode++;
int tmp = stack.back();
do{
tmp = stack.back();
v2[tmp].push_back(ctnode);
v2[ctnode].push_back(tmp);
stack.pop_back();
}while(tmp != i);
v2[cur].push_back(ctnode);
v2[ctnode].push_back(cur);
}
}
void dfs(int cur, int fa){
dep[cur] = dep[fa] + 1;
father[cur][0] = fa;
for(int i = 1; i <= M; i++){
father[cur][i] = father[father[cur][i - 1]][i - 1];
}
for(int i:v2[cur]){
if(i == fa) continue;
dfs(i, cur);
}
}
int lca(int x, int y){
if(x == y) return x;
if(dep[x] < dep[y]) std::swap(x, y);
for(int i = M; i >= 0; i--){
if(dep[father[x][i]] >= dep[y]) x = father[x][i];
}
if(x == y) return x;
for(int i = M; i >= 0; i--){
if(father[x][i] != father[y][i]){
x = father[x][i];
y = father[y][i];
}
}
return father[x][0];
}
void dfs2(int cur, int fa){
for(int i:v2[cur]){
if(i == fa) continue;
dfs2(i, cur);
tr[cur] += tr[i];
}
if(cur <= n) ans[cur] = firstans - tr[cur] + 1;
}
void solve(){
std::cin >> n >> m >> siza;
for(int i = 1; i <= n; i++){
ans[i] = -1;
}
for(int i = 1; i <= siza; i++){
std::cin >> a[i];
flag[a[i]] = 1;
}
for(int i = 1; i <= m; i++){
int x, y;
std::cin >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
ctnode = n;
tarjan(1);
dfs(1, 1);
for(int i = 1; i <= siza; i++){
int cur = -1;
for(int j:v[a[i]]){
if(!dfn[j]) continue;
if(cur == -1) cur = j;
else cur = lca(cur, j);
}
if(cur != -1) firstans++, tr[cur]++;
}
dfs2(1, 0);
for(int i = 1; i <= n; i++){
if(!flag[i] && ans[i] == -1) ans[i] = firstans;
}
for(int i = 1; i <= n; i++){
std::cout << ans[i] << ' ';
}
std::cout << '\n';
for(int i = 0; i <= ctnode; i++){
flag[i] = 0;
ans[i] = 0;
low[i] = dfn[i] = 0;
v[i].clear();
v2[i].clear();
dep[i] = 0;
for(int j = 0; j <= M; j++){
father[i][j] = 0;
}
tr[i] = 0;
ans[i] = 0;
}
curdfn = firstans = 0;
}
}
时间复杂度：。
有帮助，赞一个