边双连通分量¶
边双连通分量（Edge-Biconnected Component）是图论中的一个概念，它指的是在一个无向图中，极大的一组顶点和边，使得任意两个顶点间都有至少两条不相交的边连接（即即使删除图中的一条边，这些顶点仍然是连通的）。换句话说，边双连通分量中的任意两个顶点间都是边双连通的。
例题 #1¶
对于一个 \(n\) 个节点 \(m\) 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。
提示&代码
void tarjan(int u,int eid) {//当前节点,入边编号
dfn[u]=low[u]=++indx;
stk[++tp]=u;
for(int i=head[u]; ~i; i=edge[i].nxt) {
int v=edge[i].to;
if(dfn[v]==0) {
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
edcc++;
int x;
do {
x=stk[tp--];
belong[x]=edcc;
} while(x!=u);
}
}
完整代码
/*////////ACACACACACACAC///////////
. Code by Ntsc .
. Earn knowledge .
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;
const int N=5e5+5;
const int M=5e6;
const int Mod=1e5;
const int INF=1e5;
int n,m,p,T;
int dfn[N],low[N],indx;//时间戳，追溯值，给时间戳编号的计数器
int stk[N],tp;//栈，指针
bool instk[N]; //是否在栈中
int belong[N],siz[N],edcc; //记录每个点在那个边双连通分量里, 每个点所在的边双连通分量的大小,边双连通分量的数量
vector<int> ans[N];
int vis[N];
struct edge{
int to,nxt;
}e[M];
int h[N],idx=-1;
void add(int a,int b){
e[++idx]={b,h[a]};
h[a]=idx;
e[++idx]={a,h[b]};
h[b]=idx;
}
void tarjan(int u,int eid) {//当前节点,入边编号
vis[u]=1;
dfn[u]=low[u]=++indx;
stk[++tp]=u;
for(int i=h[u]; ~i; i=e[i].nxt) {
int v=e[i].to;
if(dfn[v]==0) {
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
edcc++;
int x;
do {
x=stk[tp--];
belong[x]=edcc;
} while(x!=u);
}
}
signed main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=N;i++)e[i].nxt=-1,h[i]=-1;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++)if(!vis[i])tarjan(i,0);//图可能不连通！切勿重复访问！
for(int i=1;i<=n;i++)ans[belong[i]].push_back(i);
cout<<edcc<<endl;
for(int i=1;i<=edcc;i++){
cout<<ans[i].size()<<' ';
for(auto v:ans[i])cout<<v<<' ';
cout<<endl;
return 0;
}
例题 #2「EVOI-RD2」旅行家¶
题目描述
小 A 是一个热衷于旅行的旅行家。有一天，他来到了一个城市，这个城市由 \(n\) 个景点与 \(m\) 条连接这些景点的道路组成。每个景点有一个**美观度** \(a_i\)。
定义一条**旅游路径**为两个景点之间的一条非严格简单路径，也就是点可以重复经过，而边不可以。
接下来有 \(q\) 个旅游季，每个旅游季中，小 A 将指定两个顶点 \(x\) 和 \(y\)，然后他将走遍 \(x\) 到 \(y\) 的**所有旅游路径**。
所有旅游季结束后，小 A 会统计他所经过的所有景点的美观度之和（重复经过一个景点只统计一次美观度）。他希望你告诉他这个美观度之和。
输入格式
第一行两个正整数 \(n,m\)。
第二行 \(n\) 个正整数 \(a_i\)，代表顶点 \(i\) 的权值。
接下来 \(m\) 行，每行 \(2\) 个正整数，表示一条无向边的两个端点。
然后一个正整数 \(q\)，代表有 \(q\) 个旅游季。
接下来 \(q\) 行，每行 \(2\) 个整数 \(x,y\)，表示指定的起点和终点。
格式
一行，一个整数表示最终的美观度总和。
对于 \(100\%\) 的数据，保证 \(3 \leq n \leq 5 \times 10^5\)，\(m \leq 2 \times 10^6\)，\(q=10^6\)，\(1 \leq a_i \leq 100\)，且该图联通，没有重边和自环。
我们发现，x 到 y 的所有旅游路径可能经过的点就是edcc缩点后x,y路径上的所有点集。那么我们问题就变成了缩点后树上路径加，这个用树上差分简单解决。
本题存在重边。每个 dfs 都需要使用 vis 判重边，否则可以被卡到 \((\frac{M}{N})^N\)。可参考下图自行模拟。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
// using fread
#define INPUT_OPTIMIZE
// using fwrite
#define OUTPUT_OPTIMIZE
namespace IO { //新的IO优化
#ifdef INPUT_OPTIMIZE
#ifdef __unix__
#include<sys/mman.h>
inline static const char *_read_ptr = (const char *)mmap(nullptr, 0x7fffffff, 1, 2, 0, 0);
#define getchar() (*_read_ptr++)
#else
static char buf[1<<21/*如不对请调整buf和fread的长度,write部分同上*/], *p1 = buf, *p2 = buf;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
#endif
#endif
inline bool read(char *t) {
memset(t, 0, sizeof t);
char *pd = t, c = getchar();
while (isspace(c)) c = getchar();
while (!isspace(c)) *pd++ = c, c = getchar();
return c == EOF;
}
template <typename T>
inline bool read(T &t) {
t=0;T sgn=1;
char c = getchar();
while (!isdigit(c)) {if(c == '-')sgn *= -1;c = getchar();}
while (isdigit(c)) t = (t << 3) + (t << 1) + (c ^ 48), c = getchar();
t*=sgn;
return c == EOF;
}
template <typename T, typename... Args>
inline bool read(T &t, Args&... args) {
return read(t) ? 1 : read(args...);
}
#ifdef OUTPUT_OPTIMIZE
static char outbuf[1<<21], *out = outbuf;
#define putchar(x) *out++ = x
#define flush() fwrite(outbuf, 1, out - outbuf, stdout)
#else
#define flush() 0
#endif
template
<typename T>
inline
void write(T x) {
if (!x) return putchar('0'), void();
static char t[9], p = 0;
while (x) t[++p] = (x % 10) ^ 48, x /= 10;
while (p) putchar(t[p--]);
}
}
using namespace IO;
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 4e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
struct edge{
int v,id,nxt;
}e[N],g[N];
int h[N],hg[N];
// vector<edge> e[N];
int idx;
void add(int a,itn b,int id){
e[++idx]={b,id,h[a]};
h[a]=idx;
e[++idx]={a,id,h[b]};
h[b]=idx;
}
int dfn[N],tim;
int edcc[N],edccCnt;
int sz[N];
int low[N];
int a[N];
void addg(int a,int b){
g[++idx]={b,0,hg[a]};
hg[a]=idx;
g[++idx]={a,0,hg[b]};
hg[b]=idx;
}
itn stk[N],top;
void tarjan(int x,int id){
//edcc
dfn[x]=low[x]=++tim;
stk[++top]=x;
for(int i=h[x];i;i=e[i].nxt){
auto v=e[i];
if(!dfn[v.v]){tarjan(v.v,v.id);low[x]=min(low[x],low[v.v]);}
if(v.id!=id)low[x]=min(low[x],dfn[v.v]);
}
if(dfn[x]==low[x]){
edccCnt++;
int y;
do{
y=stk[top--];
edcc[y]=edccCnt;
sz[edccCnt]+=a[y];
}while(y!=x);
}
}
int n,m;
namespace LCA{
int dep[N],fa[N][22],VIS[N];
int cnt=0;
void dfs(int x,int f){
if(VIS[x]) return;
VIS[x]=1;
dep[x]=dep[f]+1;
++cnt;
for(int i=hg[x];i;i=g[i].nxt){
int v=g[i].v;
if(v==f||g[i].id)continue;
fa[v][0]=x;
for(int j=1;j<20;j++){
fa[v][j]=fa[fa[v][j-1]][j-1];
}
dfs(v,x);
}
}
int lca(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;~i;--i)
if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
for(int i=19;~i;--i)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
}using namespace LCA;
int c[N];
// unordered_map<int,map<int,int> > conn;
bitset<N> vis;
void dfs2(int x,int f){
vis[x]=1;
for(int i=hg[x];i;i=g[i].nxt){
int v=g[i].v;
if(v==f||vis[v])continue;
dfs2(v,x);
c[x]+=c[v];
}
}
void solve(){
read(n,m);
for(int i=1;i<=n;i++){
read(a[i]);
}
int u,v;
for(int i=1;i<=m;i++){
read(u,v);
add(u,v,i);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
idx=0;
for(int i=1;i<=n;i++){
for(int j=h[i];j;j=e[j].nxt){
auto v=e[j];
if(edcc[i]!=edcc[v.v])addg(edcc[i],edcc[v.v]);
}
}
dfs(1,0);
int q;
read(q);
int x,y;
while(q--){
read(x,y);
x=edcc[x];
y=edcc[y];
int anc=lca(x,y);
// cdbg(x,y,anc);
c[x]++;
c[y]++;
c[anc]--;
c[fa[anc][0]]--;
}
dfs2(1,0);
int ans=0;
for(int i=1;i<=edccCnt;i++){
if(c[i]>0)ans+=sz[i];
}
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
边双连通分量和点双连通分量的区别¶
在多数图中，两者看起来没有什么区别。两者的主要区别在于：
若两个边双连通分量之间有1个公共点，则它们组成一个更大的边双连通分量。
若两个点双连通分量之间有2个公共点，则它们组成一个更大的点双连通分量。