B3610 [图论与代数结构 801] 无向图的块 题解

B3610 [图论与代数结构 801] 无向图的块 题解

2023 2023 2023，再见。 2024 2024 2024，你好！

解法

其实就是统计点双连通分量的个数。需要注意的是，孤立点在这里不被看作块。本文使用 tarjan 算法来解决这道题。

概念明晰

• 时间戳：这里记为 d f n i dfn_i dfni​，表示第一次深度优先搜索到节点 i i i 的时间。时间 t i m e ∈ N + time \in \mathbb{N}^+ time∈N+ 且随这搜索依次递增。
• 搜索树：从选定的节点出发的深搜，每个节点仅搜索一次，把所有搜索路径组成一颗树，称为搜索树。如果给定的图不是一整个连通图，则称为搜索森林。
• 追溯值：这里记为 l o w i low_i lowi​，表示节点 i i i 最多经过一条返祖边能走到搜索树中以 i i i 的子树中的节点的最小 d f n dfn dfn 为多少（简洁的定义出自东灯的博客）。
• 割点：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点。

追溯值的计算

首先根据定义， l o w i low_i lowi​ 的初始值应赋为 d f n i dfn_i dfni​。现在考虑怎么进一步更新 l o w i low_i lowi​。

• 如果在搜索树上 i i i 是 j j j 的父节点，则 l o w i = min ⁡ ( l o w i , l o w j ) low_i = \min(low_i,low_j) lowi​=min(lowi​,lowj​)。
• 如果从 i i i 到 j j j 的连边不是搜索树上的边，则 l o w i = min ⁡ ( l o w i , d f n j ) low_i= \min(low_i,dfn_j) lowi​=min(lowi​,dfnj​)。

割点的判定方法

定义搜索树中节点 i i i 的子树为 s o n i son_i soni​。

• 如果 i i i 不是搜索树的根，则当 ∃ d f n i ≤ l o w j , j ∈ s o n i \exists dfn_i \le low_j,j \in son_i ∃dfni​≤lowj​,j∈soni​ 时， i i i 是割点。
• 如果 i i i 是搜索树的根，则当有两个不同的 j j j 满足上述条件时， i i i 是割点。

判定方法的证明

如果 d f n i ≤ l o w j dfn_i \le low_j dfni​≤lowj​，则证明从 j ∈ s o n i j \in son_i j∈soni​ 出发，不经过点 i i i 无论如何也不能到达 i i i 的祖先。所以如果把 i i i 删去，则 s o n i son_i soni​ 就会与原图分离。

代码

#include<bits/stdc++.h>
using namespace std;
#define Getchar() p1==p2 and (p2=(p1=Inf)+fread(Inf,1,1<<7,stdin),p1==p2)?EOF:*p1++
#define Putchar(c) p3==p4 and (fwrite(Ouf,1,1<<7,stdout),p3=Ouf),*p3++=c
char Inf[1<<7],Ouf[1<<7],*p1,*p2,*p3=Ouf,*p4=Ouf+(1<<7);
inline void read(int &x,char c=Getchar())
{
	bool f=c!='-';
	x=0;
	while(c<48 or c>57) c=Getchar(),f&=c!='-';
	while(c>=48 and c<=57) x=(x<<3)+(x<<1)+(c^48),c=Getchar();
	x=f?x:-x;
}
inline void write(int x)
{
	if(x<0) Putchar('-'),x=-x;
	if(x>=10) write(x/10),x%=10;
	Putchar(x^48);
}
struct my_stack
{
	int top,a[500010];
	inline int size()
	{
		return top;
	}
	inline int &operator[](const int &x)
	{
		return a[x];
	}
	inline int back()
	{
		return a[top];
	}
	inline void push_back(const int &x)
	{
		a[++top]=x;
	}
	inline void pop_back()
	{
		top--;
	}
	inline void clear()
	{
		top=0;
	}
};
my_stack v;
int n,m,head[500010],cnt,dfn[500010],low[500010],times,belong[500010],tot;
vector<int> ans[500010];
struct edge
{
	int to,next;
};
edge e[4000010];
inline void add(const int &x,const int &y) noexcept
{
	e[++cnt].to=y,e[cnt].next=head[x],head[x]=cnt;
}
inline void tarjan(const int &pos,const int &fa)
{
	int son=0;
	dfn[pos]=low[pos]=++times,v.push_back(pos);
	for(int i=head[pos];i;i=e[i].next)
		if(!dfn[e[i].to])
		{
			son++,tarjan(e[i].to,pos),low[pos]=min(low[pos],low[e[i].to]);
			if(low[e[i].to]>=dfn[pos])
			{
				tot++;
				while(v[v.top+1]!=e[i].to) ans[tot].push_back(v.back()),v.pop_back();
				ans[tot].push_back(pos);
			}
		}else if(e[i].to!=fa) low[pos]=min(low[pos],dfn[e[i].to]);
}
int main()
{
	read(n),read(m);
	for(int i=1,x,y;i<=m;i++) read(x),read(y),add(x,y),add(y,x);
	for(int i=1;i<=n;i++) if(!dfn[i]) v.clear(),tarjan(i,0);
	for(int i=1;i<=tot;i++) std::sort(ans[i].begin(),ans[i].end());
	std::sort(ans+1,ans+tot+1,[](std::vector<int> &lhs,std::vector<int> &rhs)
	{
		for(int i=0;i<std::min(lhs.size(),rhs.size());i++) if(lhs[i]!=rhs[i]) return lhs[i]<rhs[i];
		return lhs.size()<rhs.size();
	});
	write(tot),Putchar('\n');
	for(int i=1;i<=tot;i++,Putchar('\n'))
	{
		for(int j=0;j<ans[i].size();j++) write(ans[i][j]),Putchar(' ');
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}