姓名： 张瑜
赛道： 提高组
类型： 算法技能
Tarjan学习笔记
内容概要
dfs 搜索树
首先，我们要知道，Tarjan 算法来源于搜索树，那是什么呢，顾名思义就是按照搜索的顺序来遍历，所产生的顺序构成的树。首先我们可以来举个有向图的例子：
所以我们可以知道 dfs 生成树有一下 4 种边：
- 树边（tree edge）：图中黑色边表示。表示搜索访问到未访问过的结点。
- 回祖边（back edge）：图中橙色边表示。表示该边指向先前访问过的祖先。
- 叉边（横向边）（cross edge）：图中蓝色边表示。表示该边指向先前访问过的非祖先结点。
- 前向边（forward edge）：图中红色边表示。表示该边指向先前访问过的孩子结点。
但是，虽然有向图有四种，可是无向图却只有 2 种，分别是树边和回祖边。这里就不举例子了。
如果有人问为什么无向图偏偏少了叉边和前向边呢？好，我们来证明一下。
- 如果存在叉边 u \Rightarrow v ，其中 u 为当前搜索访问到的点， v 为之前访问过的非祖先节点，那么我们根据定义可知，访问 v 的时候，就应该访问过 u 了。但是这就与 u 的定义所矛盾，所以不存在叉边。
- 如果存在前向边 u \Rightarrow v ，那么在访问 v 时，该边就会变成一条回祖边指向 u ，不会作为一条前向边。
好，那知道了 dfs 搜索树，接下来就可以学习 tarjan 了。
Tarjan
桥
然后我们先说一下桥的定义：无向图中，若删去一条边会使得这个图的极大连通分量数增加，则该边被称为桥。
也可以理解为无向图的一个连通块中，若删除一条边会使得至少两点之间无法相互到达，该边被称为桥。我们不妨讲得形象一点，也就是你去西湖，有苏堤对吧，如果我用大炮把苏堤炸了，是不是你也就无法走进去了，对吧？
也就是分成了一个外围，一个内湖，所以说苏堤就可以算一个桥。好我们来举个例子：
那么，也就是在以上这个图中： 1 \Rightarrow 2 和 5 \Rightarrow 6 就是这个图的桥。而且我们不难发现一个非常有用的结论：只有树边才可以成为桥，而回边 4 \Rightarrow 2 和 2 \Rightarrow 3 \Rightarrow 5 \Rightarrow 4 沿途上的树边都不可以成为桥，因此我们可以知道：只有一条不能被回边标记的树边才有可能成为桥。
但是，我们怎么用 Tarjan 算法来求桥呢？我们可以对每个点 u 按 dfs 序打上时间戳 dfn_u ，同时记录 low_u 表示 u 不经过他的父亲能到达最小的时间戳。那么一条树边 u \Rightarrow v 不被回边标记的充要条件就是 low_v>dfs_u 。比如
low[2]=2,dfn[1]=1;
所以 1 \Rightarrow 2 就是一座桥。代码如下：
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++num; // 初始化为num+1，表示已访问
for (int i = head[u]; i; i = e[i].next) { // 遍历 u 所有邻接点
int v = e[i].to; // 边的终点
if (v == fa) continue;
if (!dfn[v]) { // v 未访问
tarjan(v, u); // 处理下一节点
low[u] = min(low[u], low[v]); // 更新追溯值low[u]
if (low[v] > dfn[u]) // 边(u,v)是桥
cout << u << "——>" << v << endl; // 输出结果
}
else // 如果v已经被访问过
low[u] = min(low[u], dfn[v]); // 更新当前节点u的追溯点值low[u]
}
}
割点
定义：无向图中，若删去一个点会使得这个图的极大连通分量数增加，这个点被称为割点。
也可以理解为无向图的一个连通块中，若删除一个点会使得至少两点之间无法相互到达，该点被称为割点。，其他的话根桥有一点点相似。
类似于上面一张图片， 2 号就是一个割点。但是我们还有一种情况也是割点，就是当 u 作为根节点时，若 u 有两个及以上的儿子时， $u$ 为割点。
代码如下：
void Tarjan(int u,int fa)
{
dfn[u]=low[u]=++id;
int child=0;
for(int i=head[u];i;i=p[i].nxt)
{
int v=p[i].to;
if(!dfn[v])
{
Tarjan(v,u);
low[u]=min(low[u],low[v]);
if(u!=root&&low[v]>=dfn[u])
point[u]=1;
if(u==root&&++child>=2)
point[u]=1;
}
else
low[u]=min(low[u],dfn[v]);
}
}
强联通分量
首先，我们要明确一个事：强连通分量（SCC，Strongly Connected Components）是在单向图中的。
强联通子图，定义为：在 单向图 中，该子图上的任意两点之间能互相到达。
强联通分量，定义为：极大连通子图。
那么这张图的强联通分量 \{ 1,2,3,4,5,6,7 \} 。
前向边是没有一点用处的，一定牢记！！！
- 如果 u 是当前 scc 中的点，那么该 scc 的节点一定在 dfs 生成树中而且是以 $u$ 为根的子树内。怎么证明呢？若存在该 scc 中的点 v 不在 u 子树内，则 u 到 v 的路径中一定存在叉边或回边，根据叉边、回边的定义，则 v 在 u 之前已经被访问过，与 $u$ 是当前 scc 第一个被访问的结点矛盾。
- 如果我们把单个节点也算作是强联通分量，那么所有的 scc 的根应该都满足 low_u=dfn_u 。
缩点
在无向图的一些问题中，若将所有 scc 合并为一个点，那么这张无向图就会变成一张有向无环图（DAG，Directed Acyclic Graph）因此我们只需保留连接两个不同 scc 的边来构成缩点后的新图。也就是把一个个环变成一个个大点。
#include<bits/stdc++.h>
#define maxn 100001
#define maxm 500001
using namespace std;
struct node{
int to,next,from;
}edge[maxm];
queue <int> q;
vector <int> cb[maxn];
vector <int> rdr[maxn];
int ans[maxn],totq,x,y,v,rd[maxn],u,n,m,sum,vis[maxn],dis_[maxn],dis[maxn];
int dfn[maxn],low[maxn],f[maxn],times,cntqq;
int stack_[maxn],heads[maxm],fuck[maxn],cnt,tot,index_;
void add(int x,int y)
{
edge[++cntqq].next=heads[x];
edge[cntqq].from=x;
edge[cntqq].to=y;
heads[x]=cntqq;
return;
}
void tuopu()
{
for(int i=1;i<=tot;i++)
{
if(rd[i]==0)
q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
ans[++totq]=u;
for(int i=1;i<=cb[u].size();i++)
{
v=cb[u][i-1];
rd[v]--;
if(rd[v]==0)q.push(v);
}
}
}
void tarjan(int x)
{
dfn[x]=low[x]=++times;
stack_[++index_]=x;
fuck[x]=1;
for(int i=heads[x];i!=-1;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else
if(fuck[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]==dfn[x])
{
tot++;
while(1)
{
vis[stack_[index_]]=tot;
dis_[tot]+=dis[stack_[index_]];
fuck[stack_[index_]]=0;index_--;
if(x==stack_[index_+1])break;
}
}
}
int main(){
memset(heads,-1,sizeof(heads));
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
for(int i=1;i<=m;i++)
{
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<=cntqq;i++){
if(vis[edge[i].from]!=vis[edge[i].to])
{
x=vis[edge[i].from];y=vis[edge[i].to];
rd[y]++;cb[x].push_back(y);rdr[y].push_back(x);
}
}
tuopu();
for(int i=1;i<=tot;i++)
{
int w=ans[i];
f[w]=dis_[w];
for(int j=1;j<=rdr[w].size();j++)
f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);
}
for(int i=1;i<=tot;i++)
sum=max(f[i],sum);
printf("%d\n",sum);
return 0;
}
双联通分量
双联通分量包含了两种，分别是点双联通分量、边双联通分量。
首先，我们先说一下定义：
-
点双联通：对于点 u 和 v ，删去图上任意一个点， u 和 v 始终连通，则称 u 和 v 点双联通。
容易发现，若一个子图点双连通，那么这个子图上肯定没有割点。
-
边双联通：对于点 u 和 v ，删去图上任意一条边， u 和 v 始终连通，则称 u 和 v 边双联通。
容易发现，若一个子图点双连通，那么这个子图上肯定没有桥。
-
点双连通分量：极大点双连通子图。
-
边双连通分量：极大边双连通子图。
那么，我们又应该怎么实现呢？
边双连通分量：在找出原图上的桥后，将其在原图中去掉，剩下的连通块即为边双连通分量。
点双联通分量：我们将每个边双看作一个新节点，原图上的桥看作连接边双之间的边，这样新图会构成一棵树。
边双实现：
int cnt;
bool vis[N];
vector <int> dcc[N];
void dfs(int u)
{
vis[u] = 1;
dcc[cnt].push_back(u);
for(int i=head[u]; i; i=e[i].nxt)
{
if(vis[e[i].v] or bridge[i]) continue;
dfs(e[i].v);
}
}
点双实现：我太菜了————QWQ
例题讲解
缩点
额，一道模版题，不说了，自己看上面。
行星与王国
这道题目其实就是求强联通分量，上面没听懂的来卡一下。好我们再次掏出一张图。
好，再来一张，不难得出下面那张图就是 dfs 生成树。然后圆圈圈出来的就是强联通分量。
再定睛一看，那一条红边就是回祖边，那么从一个点出发，一直向下遍历，然后忽得找到一个点，那个点竟然有条指回这一个点的边。说明什么，这成了一个环啦！那么，这个环上所有的点都是强联通的。
但是这只是强联通啊，我们需要求的可是强连通分量啊！QWQ
那怎么办呢？我们只需要再想一下，什么时候一个点和他的所有子孙节点中的一部分构成强连通分量？他的子孙再也没有指向他的祖先的边，却有指向他自己的边因为只要他的子孙节点有指向祖先的边，显然可以构成一个更大的强联通图。
再举一个例子，红色是强联通分量，但是蓝色只是强联通图。那么我们只需要知道这个点 u 下面的所有子节点有没有连着这个点的祖先就行了。但是呢？我们怎么知道这个点u它下面的所有子节点一定是都与他强联通的呢？但是这好像有是不对的， $自己打草稿去。那怎么办呢？开个栈记录就行了。你不早说
如果在这个点之后被遍历到的点已经能与其下面的一部分点（也可能就只有他一个点）已经构成强连通分量，即它已经是最大的。那么把它们一起从栈里弹出来就行了。好了，那么代码怎么实现呢？我们只需要开这么几个数组
- dfs_i ，表示这个点在dfs时的时间戳。
- low_i ，表示这个点以及其子孙节点连的所有点中 $dfn_i$ 最小的值
- sta_i ，表示当前所有可能能构成是强连通分量的点。
- vis_i ，表示一个点是不是在栈里面。
然后再说一下 tarjan 的步骤：
- 首先初始化 $dfn_u=low_u$ 第几个被 dfs 到
- 将 u 存入栈中，并将 vis_u 设为 true 。
- 遍历 u 的每一个能到的点，如果这个点 dfn 为 0 ，即仍未访问过，那么就对点 v 进行 dfs ，然后 low_u = \min (low_u,low_) 。
于是我们得到了一个强联通分量。还有一个特别的点：tarjan 一遍是搜不完所有的点的，因为存在一些孤立点，所以我们要对一趟跑下来还没有被访问到的点继续跑 tarjan 。而怎么判断呢？只需要看看 dfs 是否为 0 就好了。所以说 tarjan 的时间复杂度就是 O(n) 。至于为什么我就不多说了，好了，上代码。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
vector<int> g[100005];
int color[100005],dfn[200020],low[200020],sta[200020],vis[100005],cnt[100005];
int deep,top,n,m,sum,ans;
void tarjan(int u)
{
dfn[u]=++deep;
low[u]=deep;
vis[u]=1;
sta[++top]=u;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(vis[v])
{
low[u]=min(low[u],low[v]);
}
}
}
if(dfn[u]==low[u])
{
color[u]=++sum;
vis[u]=0;
while(sta[top]!=u)
{
color[sta[top]]=sum;
vis[sta[top--]]=0;
}
top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
for(int i=1;i<=n;i++)
{
cnt[color[i]]++;
}
for(int i=1;i<=sum;i++)
{
if(cnt[i]>=1)
{
ans++;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)
{
printf("%d ",color[i]);
}
}
旅行者
Cyberland 有 n 座城市，编号从 1 到 n ，有 m 条双向道路连接这些城市。第 j 条路连接城市 a_j 和 b_j 。每天，都有成千上万的游客来到 Cyberland 游玩。
在每一个城市，都有纪念品售卖，第 i 个城市售价为 w_i 。这个售价有时会变动。
每一个游客的游览路径都有固定起始城市和终止城市，且不会经过重复的城市。
他们会在路径上的城市中，售价最低的那个城市购买纪念品。
你能求出每一个游客在所有合法的路径中能购买的最低售价是多少吗？
那么这一道题目就是经典的圆方树好题了，什么是圆方树呢？还记得我们在双联通分量那一块空出来的点双吗？没错，圆方树跟点双有千丝万缕的关系好的，我们来正式讲解圆方树。然后提醒一下，这道题目需要用到：tarjan，树剖，线段树。这些如果不会的大部分可以移步我之前的总结。但是，有同学就会问了，点双和圆方树有什么关系呢？好，因为圆方树圆方树，圆方圆方，所以他的点自然就有圆形和方形了，那么对应什么呢？就是每一个点对应圆形，每一个点双联通分量就对应方形。
那么也就是说，圆方树的点数肯定小于 2n 。因为点双跟割点有关，而割点的数量总是小于 n 。所以就有一个坑点：所有数组的大小必须开2倍。这时肯定有聪明的同学发现了，这个圆方树，看起来是树，事实上其实只有原图联通，圆方树才是一棵树。而且如果原图有 k 个连通分量，则它的圆方树也会形成 k 棵树形成的森林。好的，那么定义说完了，接下来我们就说一下怎么构造。如果说它不是联通图，那么就把它分成几个连通图。所以我们就只讨论连通图的问题，但是因为圆方树是基于点双连通分量的，而点双连通分量又基于割点，所以只需要用类似求割点的方法即可，而割点又用的是 tarjan 。所以根据理论来说，只要你会割点，那么你就会圆方树。好，首先，我们首先 dfs 一遍图，构造出 dfs 生成树，跟 tarjan 迷之相似，定义的数组 dfn,low 跟 tarjan 中的一模一样，不做过多赘述，接下来来考虑点双和 DFS 树以及这两个数组之间的关联。不难发现，每个点双在 DFS 树上是一棵连通子树，并至少包含两个点。但是有一个反例，最顶端节点仅往下接一个点。同时还可以发现每条树边恰好在一个点双内。不得不评论一句，谁发明了这个算法，这么牛逼！！！%%%我们先考虑一个点双在 DFS 树中的根 u 在 u 这个地方确定点双联通分量，为什么呢？因为 u 包含了所有他的子树的信息，所以 dfs 中可以确定哪里存在点双，但是不能确定点双的点集合，但是我们要用啊？所以我们只需要略微地想亿想，就知道可以用 stl 中的栈，存储还未确定所属点双（可能有多个）的节点。那该怎么处理呢？在找到点双 u 以外的其他的点都集中在栈顶端，只需要不断弹栈直到弹出 为止即可。好的，那么我们就完成了圆方树的构建了。好，那么这一道题目基本上差不多就完成了，就是建一个圆方树再用树链剖分和线段树维护一下就好了。OK，很不容易啊。我们上代码：
#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
vector<int>G1[200010],G2[200010];
multiset<int>S[200010];
int minn[800010];
int dep[200010],f[200010],siz[200010],id[200010],cnt,h[200010],top[200010],loc[200010];
int pos,dfn[200010],low[200010],topp,sta[200010];
int n,m,q,dis[200010],ext;
void swap(int &x,int &y){
int t=x;x=y;y=t;
}
int min(int a,int b){
return a<b?a:b;
}
void build_tree(int o,int l,int r){
if(l==r){
minn[o]=dis[loc[l]];
return ;
}
int mid=l+r>>1;
build_tree(o<<1,l,mid);
build_tree(o<<1|1,mid+1,r);
minn[o]=min(minn[o<<1],minn[o<<1|1]);
}
void update(int o,int l,int r,int x,int k){
if(l==r){
minn[o]=k;
return ;
}
int mid=l+r>>1;
if(x<=mid)update(o<<1,l,mid,x,k);
else update(o<<1|1,mid+1,r,x,k);
minn[o]=min(minn[o<<1],minn[o<<1|1]);
}
int query(int o,int l,int r,int x,int y){
if(x<=l&&r<=y)
return minn[o];
int mid=l+r>>1,ret=INF;
if(x<=mid)ret=min(ret,query(o<<1,l,mid,x,y));
if(mid<y)ret=min(ret,query(o<<1|1,mid+1,r,x,y));
return ret;
}
void dfs1(int x,int fa){
f[x]=fa;
dep[x]=dep[fa]+1;
siz[x]=1;
int tmp=-1;
for(int i=0;i<G2[x].size();i++){
int v=G2[x][i];
if(v==fa)
continue;
dfs1(v,x);
siz[x]+=siz[v];
if(siz[v]>tmp){
tmp=siz[v];
h[x]=v;
}
}
}
void dfs2(int x,int fa){
top[x]=fa;
id[x]=++cnt;
loc[cnt]=x;
if(!h[x])
return ;
dfs2(h[x],fa);
for(int i=0;i<G2[x].size();i++){
int v=G2[x][i];
if(v==f[x]||v==h[x])
continue;
dfs2(v,v);
}
}
void tarjan(int x){
dfn[x]=low[x]=++pos;
sta[++topp]=x;
for(int i=0;i<G1[x].size();i++){
int v=G1[x][i];
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
if(low[v]==dfn[x]){
ext++;
for(int j=0;j!=v;topp--){
j=sta[topp];
G2[ext].push_back(j);
G2[j].push_back(ext);
}
G2[ext].push_back(x);
G2[x].push_back(ext);
}
}
else low[x]=min(low[x],dfn[v]);
}
}
int querypath(int x,int y){
int ret=INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ret=min(ret,query(1,1,ext,id[top[x]],id[x]));
x=f[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ret=min(ret,query(1,1,ext,id[x],id[y]));
if(x>n)
ret=min(ret,dis[f[x]]);
return ret;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
ext=n;
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
G1[u].push_back(v);
G1[v].push_back(u);
}
tarjan(1);
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)
if(f[i])
S[f[i]].insert(dis[i]);
for(int i=n+1;i<=ext;i++)
dis[i]=*S[i].begin();
build_tree(1,1,ext);
while(q--){
char s[5];
scanf("%s",s);
if(s[0]=='C'){
int x,y;
scanf("%d%d",&x,&y);
update(1,1,ext,id[x],y);
if(f[x]){
S[f[x]].erase(S[f[x]].lower_bound(dis[x]));
S[f[x]].insert(y);
if(dis[f[x]]!=*S[f[x]].begin()){
dis[f[x]]=*S[f[x]].begin();
update(1,1,ext,id[f[x]],dis[f[x]]);
}
}
dis[x]=y;
}
else if(s[0]=='A'){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",querypath(x,y));
}
}
return 0;
}
