割点与桥
定义
对于一个无向图，如果将一个点及其相连的边去掉后连通块数量增加，这个点就是割点；如果去掉一个边后连通块数量增加，这条边就是桥，也称割边。
求法
对无向图的每个连通块 DFS。求出每个点的 DFS 序和追溯值 low。一个点的追溯值定义为在搜索树上它的子树中的点和与这些点用一条边相连的点的 DFS 序的最小值。
void dfs(int u){
dfn[u]=low[u]=++tot;
for(int v:e[u])if(check(u,v)){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfs(v);low[u]=min(low[u],low[v]);
}
}
}
其中 check(u,v) 需视具体情况而定，一般取 fa[u]!=v。但是求桥时为了考虑重边的情况，需要改成不经过已经走过的边。求割点时为了方便还可以不设置 check，这时 low[v] 显然小于等于 dfn[u]。
当 \(\rm{dfn}_u<\rm{low}_v\) 时，边 \((u,v)\) 为桥。
当搜索树上 \(u\) 不是根且在其儿子中至少存在一个点 \(v\) 使得 \(\rm{dfn_u}\le\rm{low}_v\) 时，\(u\) 是割点。
当搜索树上 \(u\) 是根且在其儿子中至少存在两个点 \(v\) 使得 \(\rm{dfn}_u\le\rm{low}_v\) 时，\(u\) 是割点。
上面结论的证明都十分显然。如果你在求割点时不设置 check，判定也可以写成 \(\rm{dfn}_u=\rm{low}_v\)。
例题
P3388 【模板】割点（割顶）
题意就是让你输出割点。
#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e4+5;
int n,m,dfn[N],low[N],tot;
vector<int>e[N],ans;
void dfs(int u,int fa){
dfn[u]=low[u]=++tot;int cnt=0;
for(int v:e[u])if(v!=fa){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfs(v,u);low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v])cnt++;
}
}
if((fa&&cnt)||cnt>1)ans.push_back(u);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0);
sort(ans.begin(),ans.end());
cout<<ans.size()<<'\n';
for(int i:ans)cout<<i<<' ';
return 0;
}
P8436 【模板】边双连通分量
边双连通分量，简称 e-DCC。
顾名思义，边双联通分量就是无向图中的一个极大子图，满足边双连通。
那么边双连通又可以顾名思义，就是两个点可以通过两条没有边相交的路径相连。
于是我们得出结论：桥连接了不同的边双连通分量。
然后这道题让我们求所有 e-DCC。那就很容易了。
#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,dfn[N],low[N],tot,totans;
vector<pair<int,int>>e[N];
vector<int>ans;bool vis[N],brg[N<<2];
void dfs(int u,int lst){
dfn[u]=low[u]=++tot;
for(auto[v,w]:e[u])if(w!=lst){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfs(v,w);low[u]=min(low[u],low[v]);
if(dfn[u]<low[v])brg[w]=1,totans++;
}
}
}
void getans(int u){
ans.push_back(u);vis[u]=1;
for(auto[v,w]:e[u])if(!vis[v]&&!brg[w])getans(v);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e[u].emplace_back(v,i);
e[v].emplace_back(u,i);
}
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i,0),totans++;
printf("%d\n",totans);
for(int i=1;i<=n;i++)if(!vis[i]){
ans.clear();getans(i);
printf("%lu",ans.size());
for(int j:ans)printf(" %d",j);
puts("");
}
return 0;
}
P8435 【模板】点双连通分量
点双连通分量，简称 v-DCC。
顾名思义，点双联通分量就是无向图中的一个极大子图，满足点双连通。
那么点双连通又可以顾名思义，就是两个点可以通过两条没有点相交的路径相连。
于是我们得出结论：割点连接了不同的点双连通分量。
然后这道题让我们求所有 v-DCC。那就很容易了。
好像不是那么容易。割点可能在不同的 v-DCC 中同时出现，并且相连的边在同一个 v-DCC 中可能有多条。你不能保证割点不被重复统计或者漏算。
我们可以用一个栈来解决问题，找到割点时把下面那一棵子树弹出来作为一个新的 v-DCC，同时不要忘了加入割点本身但是不弹出割点。具体见代码。
#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,dfn[N],low[N],tot,sta[N],top;
vector<int>e[N];vector<vector<int>>ans;
void dfs(int u){
dfn[u]=low[u]=++tot;sta[++top]=u;
for(int v:e[u]){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfs(v);low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){
vector<int>a;sta[top+1]=0;
while(sta[top+1]!=v)a.push_back(sta[top--]);
a.push_back(u);ans.push_back(a);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
if(u==v)continue;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i]){
if(e[i].empty())ans.push_back({i});
else top=0,dfs(i);
}
printf("%lu\n",ans.size());
for(auto a:ans){
printf("%lu ",a.size());
for(int i:a)printf("%d ",i);
puts("");
}
return 0;
}
圆方树
概念
圆方树是个很有用的东西，可以用来维护仙人掌，不过我现在暂时没有做过这类题目。我以前以为圆方树就是把 v-DCC 缩点之后形成的树。
圆方树的圆点是原来的无向图中的点。在无向图中每发现一个 v-DCC 就加入一个方点，将这个新的方点与这个 v-DCC 中的所有圆点连边。这些新的边就和圆点、方点一起构成了圆方树。代码详见例题。
于是有一个很显然的性质：一条边连接的一定是圆点和方点。
圆方树可以很好地处理无向图中的简单路径（不重复经过某个点的路径）的问题。
例题
P4630 [APIO2018] 铁人两项
题意：求一张 \(n\) 个点 \(m\) 条边的无向图中有多少有序点对 \((x,y,z)\) 满足三点互不相同且存在一条起点为 \(x\)，终点为 \(z\)，经过 \(y\) 的简单路径。\(n\le10^5,m\le2\times10^5\)。
题解：考虑确定 \(x,z\)，求 \(y\) 的取值数量。不难发现建立圆方树后，这个值就相当于 \(x,z\) 的简单路径上方点对应的 v-DCC 的并集减去 \(x,z\) 的大小。我们可以给每个点赋权值：圆点权值为 \(-1\)，方点权值为其对应的 v-DCC 的大小。这样，\(y\) 的取值数量就是 \(x,z\) 的简单路径上所有点的权值和。
那么一个点对答案的贡献就是它的权值乘以经过它的路径条数。
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;
int n,m,dfn[N],low[N],tot,cnt,sta[N],top,siz[N<<1],Sz,w[N<<1];
vector<int>G[N],T[N<<1];long long ans;
void dfsGraph(int u){
dfn[u]=low[u]=++tot;sta[++top]=u;Sz++;w[u]=-1;
for(int v:G[u]){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfsGraph(v);low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
w[++cnt]=1;
for(int x=0;x!=v;top--){
x=sta[top];w[cnt]++;
T[cnt].push_back(x);
T[x].push_back(cnt);
}
T[cnt].push_back(u);
T[u].push_back(cnt);
}
}
}
}
void dfsTree(int u,int fa){
siz[u]=(u<=n);
for(int v:T[u])if(v!=fa){
dfsTree(v,u);
ans+=2ll*siz[v]*siz[u]*w[u];
siz[u]+=siz[v];
}
ans+=2ll*siz[u]*(Sz-siz[u])*w[u];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;cnt=n;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i]){
top=Sz=0;dfsGraph(i);dfsTree(i,0);
}
cout<<ans<<'\n';
return 0;
}
CF487E Tourists
题意：维护一个 \(n\) 个点 \(m\) 条边的无向图，点有点权。\(Q\) 次操作，每次操作可以修改某一点的点权，或者询问两点之间的所有简单路径能经过的点中权值最小的点的权值。\(n,m,Q\le 10^5\)。
题解：建出圆方树后，将方点的点权赋为其子节点的权值的最小值。这样，每当修改圆点的点权时，只需修改其父亲的权值。查询时若两点 LCA 为方点，再算上 LCA 的父亲。树剖维护就行了。
#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
int n,m,Q,dfn[N],low[N],tot,cnt,sta[N],tp,w[N];
int wi[N],fa[N],siz[N],son[N],id[N],top[N],dep[N],dat[N<<2];
vector<int>G[N],T[N];multiset<int>s[N];
void dfsGraph(int u){
dfn[u]=low[u]=++tot;sta[++tp]=u;
for(int v:G[u]){
if(dfn[v])low[u]=min(low[u],dfn[v]);else{
dfsGraph(v);low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
cnt++;
for(int x=0;x!=v;tp--){
x=sta[tp];
T[x].push_back(cnt);
T[cnt].push_back(x);
}
T[u].push_back(cnt);
T[cnt].push_back(u);
}
}
}
}
void dfs1(int u){
siz[u]=1;dep[u]=dep[fa[u]]+1;
for(int v:T[u])if(v!=fa[u]){
if(u>n)s[u].insert(w[v]);
fa[v]=u;dfs1(v);siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
if(u>n)w[u]=*s[u].begin();
}
void dfs2(int u,int topf){
wi[id[u]=++tot]=w[u];top[u]=topf;
if(!son[u])return;
dfs2(son[u],topf);
for(int v:T[u])if(v!=fa[u]&&v!=son[u])dfs2(v,v);
}
void build(int p,int l,int r){
if(l==r)return dat[p]=wi[l],void();
int mid=(l+r)>>1;
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
dat[p]=min(dat[p<<1],dat[p<<1|1]);
}
void upd(int p,int l,int r,int x,int val){
if(l==r)return dat[p]=val,void();
int mid=(l+r)>>1;
if(x<=mid)upd(p<<1,l,mid,x,val);
else upd(p<<1|1,mid+1,r,x,val);
dat[p]=min(dat[p<<1],dat[p<<1|1]);
}
int ask(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return dat[p];
int mid=(l+r)>>1,ret=1e9;
if(L<=mid)ret=min(ret,ask(p<<1,l,mid,L,R));
if(R>mid)ret=min(ret,ask(p<<1|1,mid+1,r,L,R));
return ret;
}
int query(int x,int y){
int ret=1e9;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret=min(ret,ask(1,1,cnt,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ret=min(ret,ask(1,1,cnt,id[x],id[y]));
if(x>n)ret=min(ret,w[fa[x]]);
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>Q;cnt=n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfsGraph(1);tot=0;
dfs1(1);dfs2(1,1);build(1,1,cnt);
while(Q--){
string c;int x,y;
cin>>c>>x>>y;
if(c[0]=='C'){
upd(1,1,cnt,id[x],y);
if(fa[x]){
s[fa[x]].erase(w[x]);
s[fa[x]].insert(y);
w[fa[x]]=*s[fa[x]].begin();
upd(1,1,cnt,id[fa[x]],w[fa[x]]);
}
w[x]=y;
}else printf("%d\n",query(x,y));
}
return 0;
}