图的连通性相关（Tarjan算法）
（大抄蓝书）
Part 1：无向图连通性
无向图的割点与桥
给定无向图 \(G=(V,E)\)：
-
若对于 \(x\in V\)，从图中删去节点 \(x\) 以及所有与 \(x\) 关联的边之后，\(G\) 分裂成两个或两个以上不相连的子图，则称 \(x\) 为 \(G\) 的割点
-
若对于 \(e\in E\)，从图中删去边 \(e\) 之后，\(G\) 分裂成两个不相连的子图，则称 \(e\) 为 \(G\) 的割边或桥
\(\mathrm{Tarjan}\) 算法基于无向图的深度优先遍历，能够在线性时间内求出无向图的割点和桥，进一步可求出无向图的双联通分量。下面给出一些定义及定理：
时间戳
在图的深度优先遍历中，按照每个节点第一次被访问的时间顺序，给予 \(1\dots n\) 的整数标记，该标记就被称为“时间戳”，记为 \(dfn[x]\)
搜索树
在无向联通图中任选一个节点进行深度优先遍历，每个点只访问一次，所以发生递归的边 \((x,y)\) 构成一棵树，这棵树被称为“无向联通图的搜索树”。
若无向图不连通，则各个连通块的搜索树构成无向图的“搜索森林”
追溯值
设 \(\mathrm{subtree(x)}\) 表示搜索树中以 \(x\) 为根的子树。\(x\) 的追溯值 \(low[x]\) 定义为以下节点的时间戳的最小值
- \(\mathrm{subtree(x)}\) 中的节点
- 通过 \(1\) 条不在搜索树上的边，能够达到 \(\mathrm{subtree(x)}\) 的节点
感性理解为不经过其父亲能到达的最小的时间戳。
割边判定法则
无向图 \((x,y)\) 是桥，当且仅党搜索树上存在一个 \(x\) 的子节点 \(y\)，满足：
同时可以得出一些结论：
-
桥一定是搜索树中的边
-
一个简单环中的边一定都不是桥
一道割边模板题 P1656 炸铁路
考虑一个细节：
对于边 \((x,fa)\) 来说，如果无重边，\(fa\) 的时间戳不能更新 \(low[x]\)。但如果有重边就可以。所以不能单纯在递归时单纯记录每个节点的父节点。我们可以使用成对变换技巧，沿着编号 \(i\) 的边进入节点 \(x\)，则忽略从 \(x\) 出发的编号为 \(i\:\mathrm{xor} 1\) 的边
#include<bits/stdc++.h>
using namespace std;
const int N=250,M=5010;
int n,m,dfn[N],low[N],num,cnt;
int head[N],ver[2*M],nxt[2*M],tot=1;
pair <int,int> ans[M];
bool bri[2*M];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
void add(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void tarjan(int x,int last)
{
low[x]=dfn[x]=++num;
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i];
if(!dfn[y])
{
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]) //割边判定法则
bri[i]=bri[i^1]=1;
}
else if(i!=(last^1))
low[x]=min(low[x],dfn[y]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i,0);
for(int i=2; i<=tot; i+=2)
{
if(bri[i])
{
int x=ver[i],y=ver[i^1];
if(x>y)
swap(x,y);
ans[++cnt]=make_pair(x,y);
}
}
sort(ans+1,ans+1+cnt,cmp);
for(int i=1; i<=cnt; i++)
printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}
割点判定法则
若 \(x\) 不是搜索树的根节点，则 \(x\) 是割点当且仅当搜索树上存在一个 \(x\) 的子节点 \(y\)，满足：
特别地，若 \(x\) 是搜索树的根节点，则 \(x\) 是割点当且仅当搜索树上存在至少两个子节点 \(y_1,y_2\) 满足上述条件
一道割点模板题【模板】割点（割顶）
因为割点判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从 \(x\) 出发能访问到的所有节点的时间戳都能用来更新 \(low[x]\)
#include<bits/stdc++.h>
using namespace std;
const int N=20010,M=100010;
int n,m,dfn[N],low[N],num,rt;
int head[N],ver[2*M],nxt[2*M],tot;
bool cut[N];
void add(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
int t=0;
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]) //割点判定法则
{
t++;
if(x!=rt || t>1)
cut[x]=1;
}
}
else
low[x]=min(low[x],dfn[y]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1; i<=n; i++)
if(!dfn[i])
rt=i,tarjan(i);
int cnt=0;
for(int i=1; i<=n; i++)
if(cut[i])
cnt++;
printf("%d\n",cnt);
for(int i=1; i<=n; i++)
if(cut[i])
printf("%d ",i);
return 0;
}
无向图的双联通分量
定义
-
若一张无向联通图不存在割点，则称它为“点双连通图”。若一张无向联通图不存在桥，则称它为“边双联通图”
-
无向图的极大点双联通子图被称为“点双联通分量”，简记为“\(\mathrm{v\!-\!DCC}\)”。无向图的极大边双联通子图被称为“边双连通分量”，简记为“\(\mathrm{e\!-\!DCC}\)”。二者统称为“双连通分量”，简记为“\(\mathrm{DCC}\)”
定理
一张无向联通图是“点双联通图”，当且仅当满足下列两个条件之一：
-
图中的顶点数不超过 \(2\)
-
图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环
定理
一张无向联通图是“边双连通图”，当且仅当任意一条边都包含在至少一个简单环中
边双（e-DCC）的求法
边双连通分量的计算非常简单，只需求出无向图中所有的桥，把桥都删除后，剩余的若干个连通块就是若干个“边双连通分量”
实现时，可以先用 \(\mathrm{Tarjan}\) 标记出所有桥边，再对整个图进行一次深度优先遍历（不访问桥边），用 \(c\) 数组给每个节点 \(x\) 编号即可
模板题
int c[N],dcc;
void dfs(int x)
{
c[x]=dcc;
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i];
if(c[y] || bri[i])
continue;
dfs(y);
}
}
//在main函数中
for(int i=1; i<=n; i++)
if(!c[i])
dcc++,dfs(i);
边双（e-DCC）的缩点
把每个 \(\mathrm{e\!-\!DCC}\) 看成一个点，把桥边 \((x,y)\) 看作连接编号为 \(c[x]\) 和 \(c[y]\) 的 \(\mathrm{e\!-\!DCC}\) 对应节点的无向边，产生一棵树或森林。这就是 \(\mathrm{e\!-\!DCC}\) 的缩点
int hc[N],vc[2*N],nc[2*N],tc=1;
void add_c(int x,int y)
{
vc[++tc]=y;
nc[tc]=x;
hc[x]=tc;
}
//在main函数中
for(int i=2; i<=tot; i+=2)
{
int x=ver[i^1],y=ver[i];
if(c[x]==c[y])
continue;
add_c(c[x],c[y]);
}
点双（v-DCC）
太难了，放弃，鸽在这
Part 2：有向图连通性
前置知识
给定一个有向图 \(G=(V,E)\)，若存在 \(r\in V\)，满足从 \(r\) 出发能够到达 \(V\) 中的所有点，则称 \(G\) 是一个“流图”，记为 \((G,r)\)，其中 \(r\) 称为流图的源点
在一个流图 \((G,r)\) 上从 \(r\) 出发进行深度优先遍历，每个点只访问一次，所有发生递归的边 \((x,y)\) 构成一棵以 \(r\) 为根的树，我们把它称为流图 \((G,r)\) 的搜索树
同时，类似无向图，在流图的深度优先遍历中，按照每个节点第一次被访问的时间顺序，给予 \(1\dots n\) 的整数标记，该标记被称为“时间戳”，记为 \(dfn[x]\)
流图中的每条有向边 \((x,y)\) 必然是以下四种之一：
- 树边：指搜索树中的边，即 \(x\) 是 \(y\) 的父亲
- 前向边：指搜索树中 \(x\) 是 \(y\) 的祖先
- 返祖边：指搜索树中 \(y\) 是 \(x\) 的祖先
- 横叉边：除了上述三种情况以外的边，它一定满足 \(dfn[y]<dfn[x]\)
有向图的强联通分量
-
在有向图中，若两个节点 \(x,y\) 能够相互到达，则称这两个点是强连通的，它们之间具有强连通性。
-
给定一张有向图，若对于图中任意两个节点 \(x,y\) 都是强联通的，则称该有向图是一张强连通图
-
有向图的极大强联通子图被称为“强连通分量”，简记为“\(\mathrm{SCC}\)”
\(\mathrm{Tarjan}\) 算法基于有向图的深度优先遍历，能够在线性时间内求出一张有向图的各个强联通分量。
一个“环”一定是强联通图。如果节点 \(x,y\) 强联通，那么 \(x,y\) 显然在一个环中。因此，\(\mathrm{Tarjan}\) 算法的基本思路就是对于每个点，尽量找到与它一起能构成环的所有节点
容易发现，前向边没有什么用处，而返祖边非常有用，横叉边可能有用。为了找到通过“返祖边”和“横叉边”构成的环，\(\mathrm{Tarjan}\) 算法在深度优先遍历的同时维护了一个栈。当访问到节点 \(x\) 时，栈中需要保存以下两类节点：
-
搜索树上 \(x\) 的祖先节点，记为集合 \(anc(x)\)
设 \(y\in anc(x)\)。若存在返祖边 \((x,y)\)，则 \((x,y)\) 与 \(y\) 到 \(x\) 的路径一起构成环
-
已经访问过，并且存在一条路径到达 \(anc(x)\) 的节点
设 \(z\) 是这样的一个点，从 \(z\) 出发存在一条路径到 \(t\in anc(x)\)。若存在横叉边 \((x,z)\)，则 \((x,z)\)、\(z\) 到 \(y\) 的路径，\(y\) 到 \(x\) 的路径构成一个环
综上，栈中的节点就是能与 \(x\) 出发的“返祖边”、“横叉边”形成环的节点。进而可以引入追溯值的概念
追溯值
设 \(\mathrm{subtree(x)}\) 表示流图的搜索树中以 \(x\) 为根的子树。\(x\) 的追溯值 \(low[x]\) 定义为满足以下条件的节点的最小时间戳：
- 该点在栈中
- 存在一条从 \(\mathrm{subtree(x)}\) 出发的有向边，以该点为终点
根据定义，可按照以下步骤计算“追溯值”
-
当节点 \(x\) 第一次被访问时，把 \(x\) 入栈，初始化 \(low[x]=dfn[x]\)
-
扫描从 \(x\) 出发的每条边 \((x,y)\)
- 若 \(y\) 没被访问过，说明 \((x,y)\) 是树边，递归访问 \(y\)，从 \(y\) 回溯以后，令 \(low[x]=\min(low[x],low[y])\)
- 若 \(y\) 被访问过且 \(y\) 在栈中，则令 \(low[x]=\min(low[x],dfn[y])\)
-
从 \(x\) 回溯之前，判断是否有 \(low[x]=dfn[x]\)。若成立，则不断地从栈中弹出节点，直至 \(x\) 出栈
强连通分量判定法则
在追溯值的计算过程中，若在 \(x\) 回溯前，有 \(low[x]=dfn[x]\) 成立，则栈中从 \(x\) 到栈顶的所有节点构成一个强联通分量
SCC的缩点
与 \(\mathrm{e\!-\!DCC}\) 的缩点类似，对于每条有向边 \((x,y)\)，若 \(c[x]\neq c[y]\)，则在编号为 \(c[x]\) 和 \(c[y]\) 的 \(\mathrm{SCC}\) 之间连边，最后会得到一张有向无环图
\(\mathrm{SCC}\) 缩点模板题【模板】缩点
#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=100010;
int n,m,a[N],mx;
int dfn[N],low[N],num;
int sta[N],top,ins[N],c[N],cnt,val[N];
int ans[N],p,in_deg[N],f[N];
int head[N],ver[M],from[M],nxt[M],tot;
vector <int> scc[N],g[N],gg[N];
queue <int> q;
void add(int x,int y)
{
ver[++tot]=y;
from[tot]=x;
nxt[tot]=head[x];
head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
sta[++top]=x; ins[x]=1;
for(int i=head[x]; i; i=nxt[i])
{
int y=ver[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cnt++; int y;
do
{
y=sta[top--]; ins[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
val[cnt]+=a[y];
}while(x!=y);
}
}
void topsort()
{
for(int i=1; i<=cnt; i++)
if(!in_deg[i])
q.push(i);
while(q.size())
{
int x=q.front(); q.pop();
ans[++p]=x;
for(int i=0; i<g[x].size(); i++)
{
int y=g[x][i];
in_deg[y]--;
if(in_deg[y]==0)
q.push(y);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);
for(int i=1; i<=tot; i++)
{
int x=from[i],y=ver[i];
if(c[x]==c[y])
continue;
g[c[x]].push_back(c[y]);
gg[c[y]].push_back(c[x]);
in_deg[c[y]]++;
}
topsort();
for(int i=1; i<=cnt; i++)
{
int x=ans[i];
f[x]=val[x];
for(int j=0; j<gg[x].size(); j++)
f[x]=max(f[x],f[gg[x][j]]+val[x]);
mx=max(mx,f[x]);
}
printf("%d",mx);
return 0;
}