图论笔记：直径，LCA 和 Tarjan SCC

Aw顿顿 · 2021-08-09 07:31:06 · 个人记录

一些简单的图论知识点。

树的直径

简单路径指图上任何一个节点访问至多一次的路径，而树的直径则是指一棵树上最长的简单路径。

图中所有最短路径的最大值即为「直径」，可以用两次 \texttt{DFS} 或者树形 \texttt{DP} 的方法在 O(n) 时间求出树的直径。

首先，我们需要对任意一个被选定的结点 x 去进行 \texttt{DFS} 从而求出距离它最远的结点 y。接下来所需做的便是以结点 v 为根结点再做 \texttt{DFS} 到达另一个最远结点 z。我们给定的定理内容如：第一次 \texttt{DFS} 得到的节点 y 一定处于树的直径的某一端，而第二次 \texttt{DFS} 得到的节点显而易见地处于树的直径的另一端。显然如果第一个推论成立，那么后面的结论是相应正确的，现在我们需要证明。

首先证明 \small\rm Lemma\ 1：假定我们给定一个连通但无环的图（一棵树），存在 x 与 y 的最短路和 y 与 z 的最短路不重合，那么存在 x 到 z 的最短路就是这两条路径的拼接。这是容易证明的，因为如果存在一条更短的路，那么这就出现了一个环，而这显然是有悖于题意的。

接下来我们所需要做的便是证明上述定理。

假设存在一条直径 \delta(s,t)，我们假设第一次 \texttt{DFS} 得到的点并没有存在于这两点之中，那么我们需要推导出矛盾。首选分情况讨论：如果出发点在其中之一，而到达的点不在其中之一，那么将这条边与上述直径相连接可以得到一条更长的直径，这与题设相矛盾。那如果出发点并不在两者之一呢，又应该怎么办？我们需要进一步分类。

设第一次 \texttt{DFS} 出发点是 y 并且终点是 z，假设从 y 到 z 的过程中和直径存在交点位于 x，那么我们就可以推论 \delta(y,z)=\delta(y,x)+\delta(x,z) 这是非常 Trivial 的，而我们同时可以导出的结论是 \delta(y,z)>\delta(y,t)，因为 z 是对 y 为起点进行 \texttt{DFS} 得到的最远节点。那么我们进行简单代换就会发现 \delta(x,z)>\delta(y,z)- \delta(y,x)>\delta(y,t)-\delta(y,x)=\delta(x,t)，于是我们发现该结论与题设不符，因此矛盾。

如果不存在交点，事情就更难办一些。定义 \delta(y,t) 和 \delta(s,t) 中存在的第一个交点是 x'，与此相对应地定义 \delta(y,z) 和 \delta(s,z) 中存在的第一个交点是 x。不妨看 OI-Wiki 的图：

根据我们进行 \texttt{DFS} 得到的结果，理当存在 \delta(y,z)\ge\delta(y,t) 因此可以推导出 \delta(x',x)+\delta(x,t)=\delta(x',t)\ge\delta(x',z)。如果这一结论成立，我们不难推导出 \delta(x,z)\ge\delta(x,t)，这时候我们发现实际上 s\to x\to x'\to z 是一个更合理的直径方案，因此矛盾。

综上所述，这两次 \texttt{DFS} 获得的简单路径就是直径。

给定一道例题 POJ2631 Roads in the North/UVA10308 Roads in the North，翻译化简题面如下：

有一些北方的村庄，从一个村庄到另一个村庄只有一条路线，不会经过其他村庄两次。给出的是一个由若干村庄组成的区域，这些村庄之间的道路使任何村庄都可以通过公路到达其他任何村庄。你的任务是找出该地区两个最偏远村庄之间的公路距离。

实际上就是给定一个连通图求最长路径，我们简单地使用两次 \texttt{DFS}，代码如下：

#include<bits/stdc++.h>
#define N 20005
using namespace std;
int n,m,cnt;
struct Edge{
    int v,w,nxt;
}e[N];
int h[N],ans,dis[N],pos;
void add(int u,int v,int w){
    e[++cnt].v=v;e[cnt].w=w;
    e[cnt].nxt=h[u];h[u]=cnt;
}void DFS(int x,int fa){
    if(dis[x]>ans){
        ans=dis[x];
        pos=x;
    }for(int i=h[x];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa)continue;
        dis[v]=dis[x]+e[i].w;
        DFS(v,x);
    }
}void Find(int x){
    ans=dis[x]=0;
    DFS(x,0);
}signed main(){
    int u,v,w;
    while(cin>>u>>v>>w){
        add(u,v,w);
        add(v,u,w);
    }Find(1);Find(pos);
    cout<<ans<<endl;
    return 0;
}

与最长路不同的是，这题并没有指定从 1\sim n 所以才能用上述方法。但是我们知道，两次 \texttt{DFS} 的方法并不适用于有负权的树，因此采用树形 \texttt{DP} 的方法是 \texttt{dssq}。

我们对于一个根进行 \texttt{DFS} 之后能够得到所有节点距离它的最长长度和次长长度，而我们只需要使用换根 \texttt{DP} 就能够得到剩下所有节点作为根节点时的相关信息。更具体地，我们可以比较所有的 s_1+s_2 也就是最长和次长之和，从而得到树的直径。

首先我们设 f_i 表示以 i 为根，到达其子树中叶子结点的最大距离。我们知道，从手头上处理的点 u 到最远叶子结点 v 的距离应该被表示为 \max\{w(u,x)+f_x\}，其中 x 表示 u 的叶子结点。据此，我们就得到了状态转移方程。更进一步地，树的直径应当被认为是 f_u+f_v+w(u,v)。注意应该要在更新 f_u 之前更新 ans，否则如果 f_u 经过 v 的路径是最长路径的话，这样的路径会被更新两次。

给出代码：

void dfs(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==fa)continue;
        dfs(v,u);
        ans=max(ans,f[u]+f[v]+e[i].w);
        f[u]=max(f[u],f[v]+e[i].w);
    }
}

LCA 最近公共祖先

最近公共祖先简称 LCA，有 Least/Lowest Common Ancestor 两种说法，个人认为 Lowest 的表意是较之更为妥帖的，这还有待进一步讨论。顾名思义，最近公共祖先就是两个节点 u,v 共有的所有祖先结点中距离根节点最远的（深度最大的）那一个节点。存在点集 S=\{v_i|i\in[1,n]\}，我们记这个点集的 LCA 为 \text{LCA}(S)。此处给出 LCA 的一些性质：

单个节点的 LCA 就是它本身。
两个节点 u,v 的 LCA 如果是 u，那么 u 是 v 的祖先，反之亦然。
若 u,v 分别不是对方祖先，则他们分别处于两者 LCA 的两棵子树中。
一个点集 S 的 LCA 在前序遍历中出现在点集所有元素前。
一个点集 S 的 LCA 在后序遍历中出现在点集所有元素后。
点集 s_1 和点集 s_2 并集的 LCA 等于两者分别 LCA 的 LCA。

上一条性质换言之就是 \text{LCA}(s_1\cup s_2)=\text{LCA}(\text{LCA}(u),\text{LCA}(v))

两点的 LCA 必定在两点的最短路径上。
树上两点距离等于两者深度之和减去二倍 LCA 深度。

最后一条很容易理解。我们在计算路径的时候显然不希望计算出从根节点到 LCA 的这一段路，而我们在计算两个节点深度的时候又恰巧将这一段路计算了两遍，所以我们能够写出 d(u,v)=h_u+h_v-2h_{\text{LCA}(u,v)}。

一个极端朴素的方法是每次找深度比较大的那个点，让它向上跳，等到他们相遇时就会处于 LCA 的位置上。一个类似的想法是先向上调整深度较大的点，令这两个结点深度相同 h_u=h_v，然后再共同向上跳转，最后也一定会相遇。但是这样处理太慢了——如果我们能够用一种不需要一步一步跳的方式进行深度调整和祖先寻找，那一定能够大大提高效率，这种方法就是倍增。

我们每一次需要让节点向上移动——这次移动的距离应该怎么确定？我们用二的整次幂来进行跳跃。但是我们如果使用 1,2,4,8,16 这样的跳跃顺序可能会错过终点，因此我们从大到小进行跳跃，如果当前选取的步数过大，那我们再将步数调小。很容易发现，每一种步数至多选择一次，因为如果我能够跳两次 4，那我实际上在此之前跳一次 8 就足够了，因此这个算法是 \log 级别的。

由于我们在接下来的过程中要频繁用到 \log_2(i)+1 的值，因此我们可以进行一个预处理。由于使用谓词函数后存在：

\lfloor\lg(i)\rfloor=\lg(i-1)+[2^{\lg(i-1)}=i]

我们按照这样实现可以求出来每一个数对应的 \log_2(i)+1，然后就可以放在数组里备用了。接下里使用倍增求取 LCA 需要使用一个 \rm fa 数组，接下来简写作 f，定义 f(i,j) 表示对于节点 i 而言的第 2^j 级祖先。这样的预处理需要用到深度数组 dep，这也是我们需要预处理出来的。因此我们可以考虑这样的一个思路：当前节点 u 的第 2^i 级祖先其实可以被表示为 2^{i-1} 祖先的 2^{i-1} 祖先（两步并作一步），换言之：

f(v,i)=f(f(v,i-1),i-1)

这个看似套娃的操作实际上让我们可以顺利在树上进行 DFS 预处理，因为我们对于每一次 DFS 找到的节点 u 都可以遍历从 1 到 \lg(dep_u)+1 的所有节点（之所以是遍历对数级别的节点，因为我们要更新指数级别的祖先），由此可以预处理完毕。之后再进行下一轮的递归搜索即可。给出实现代码：

void dfs(int u,int fa){
//记录各个点的深度以及他们 2^i 级的祖先 
    fa[u][0]=fa;dep[u]=dep[fa]+1;
    for(int i=1;i<=lg[dep[u]];i++){
        //对深度求对数，方便后文的 2^i 级祖先
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }for(int i=h[u];i;i=e[i].nxt)
        if(e[i].v!=fa)dfs(e[i].v,u);
}

接下来我们首先着手处理 u,v 中深度较大的那个点，不妨设 dep_u>dep_v，那我们就需要让 u 向上跳到和 v 一个高度方可进行下一番的处理。怎么办呢？由于我们在 \lg 数组中已经记录了求取对数的结果而我们的 f 数组中实际上存取的是指数级祖先，那么我们只需要以对数为下标进行倍增即可。两者深度差的对数（的下取整）作为下标，进行跳跃就可以得到一个较为优秀的复杂度。

先让 u 跳——如果跳着跳着，忽然发现 u=v 了，那么他们的 LCA 显然就是 v。因为在此时 v 是 u 的祖先，根据前面性质（或者称之为 Lemma 吧）这是成立的。现在他们两个处于同一高度了，因此我们现在需要他们两个同步按照指数进行跳跃，具体步骤如下：

取出当前跳跃下标 k=\lg(dep_u)，注意在代码实现中你得减一（因为数组中存储的是 \lg(i)+1）。
如果两者当前跳到的那个祖先不相等（那这个节点就还不是 LCA）就进行跳跃。
将 u,v 转移到 f(u,k) 和 f(v,k) 上，注意这里指他们的 2^k 级祖先。

由于之前所说的，能够跳两步解决的一定能在上一次跳一步解决，因此我们对于每一个指数都只需要跳一遍皆可。这样就可以用简单的循环实现这种倍增了，与此同时为什么我们不能判断 u=v 而是要判断 f(u,k)=f(v,k) 呢？因为我们能够同时跳到的结果并不一定是 LCA，但是这个父亲如果相等则一定是（当时神志不太清楚所以这句话是有问题，各位就把这个结论记住就行了不要理解这句话哭）。

因此我们可以实现这样的一个 LCA 代码：

int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);//保证 x 的深度大于 y 的深度 
    while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]-1];
    if(x==y)return x;//如果跳到了是同一个节点 ，这就是他们的 LCA 
    for(int k=lg[dep[x]]-1;k>=0;--k)//两人一起跳 
        if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];
    return f[x][0];
}

在这之后我们就可以写出全文代码了：

#include<bits/stdc++.h>
#define N 500005
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}int dep[N],f[N][22],lg[N],h[N],cnt,n,m,s;
struct node{int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].nxt=h[u];
    h[u]=cnt;
}void dfs(int u,int fa){
//记录各个点的深度以及他们 2^i 级的祖先 
    f[u][0]=fa;dep[u]=dep[fa]+1;
    for(int i=1;i<=lg[dep[u]];i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=h[u];i;i=e[i].nxt)if(e[i].v!=fa)dfs(e[i].v,u);
}int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);//保证 x 的深度大于 y 的深度 
    while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]-1];
    if(x==y)return x;//如果跳到了是同一个节点 ，这就是他们的 LCA 
    for(int k=lg[dep[x]]-1;k>=0;--k)//两人一起跳 
        if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];
    return f[x][0];
}signed main(){
    n=read();m=read();s=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }for(int i=1;i<=n;++i)//预处理 log_2(i)+1 的值 
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(s,0); 
    for(int i=1;i<=m;++i)printf("%lld\n",LCA(read(),read()));
    return 0;
}

注意一些普通图论题应该注意的点，比如无向边应该开两倍数组之类的。这份代码可以通过模板题。

强连通分量

如果一个有向图任意两点 x 与 y 之间，都存在一条路径，那么这个图是一个强连通的图。我们所需要求的，便是一个给定有向图中的极大强连通子图。它被称为强连通分量 SCC(Strongly Connected Component)。

给出：

例题：B3609 [图论与代数结构 701] 强连通分量

前置知识 DFS 序：给定一个图，从随意一个节点开始 DFS 会形成一棵树。

图片来自 OI-Wiki。我们发现在正常搜索的过程中，会形成一些在图中绿色的边，这些边构成了一棵树——因此我们称之为树边。显然这个图在搜索过程中会形成环，因此我们要考虑另外三种边。

如果我们访问到一个已经访问过的节点，此时我们考虑三种情况：

该节点并不是当前节点及其祖先生成的：红色横叉边
该节点在当前节点子树中：蓝色的前向边
该节点是当前节点的祖先：黄色的回边（又名返祖边）

显然，如果一个节点 u 是某个 SCC 在搜索过程中遇到的第一个节点，那么这个 SCC 的所有其余节点一定都在以这个节点为根的搜索树当中，可用反证法证明，此处略去，读者自证不难。

考虑使用 Tarjan 算法，首先定义一些变量：

以下结点之中 \text{dfn}(u) 最小的值：以 u 为根节点所在子树的所有结点，和从其子树可以由一条不在搜索树中的边连向的结点。

同时，我们在代码实现中用 in 数组来标示每一个节点属于哪一个强连通分量。我们还需要一个栈 sta 来存储尚未确定所属强连通分量的节点（也需要一个 is 数组判断当前是否在栈中）。由于我们需要记录每一个强连通分量的大小，因此我们还需要一个数组 size。

一个非常显然的事实是：节点 u 的所有子树节点的 \rm dfn 值都比 u 本身的 \rm dfn 值要大。因此从根开始的一条路径上，\rm dfn 是严格递增的，而 \rm low 则呈现出严格非下降。接下来考虑具体实现步骤。

对于一个从 u 出发访问 v 的节点，如果 v 不是其父节点，考虑三种不同的状态：

如果 v 尚未访问过，那么进一步深搜，在回溯过程中用 \text{low}(v) 更新 \text{low}(u)。
如果 v 被访问过且在栈中，那就可以用 \text{dfn}(v) 去更新 \text{low}(u) 了（考虑定义）。
如果 v 被访问过且不在栈中，那忽略（已经确定的节点无需考虑）。

给出模板题代码实现：

#include<bits/stdc++.h>
#define N 10005
#define M 100005 
using namespace std;
const int MAXN=10005;
const int MAXM=100005;
struct node{
    int v,nxt;
}e[M<<1];
int h[N],cnt,low[N],dfn[N],tot;
int in[N],f[N],n,m,ans;
bool is[N];
stack<int>s;
vector<int>vec[N];
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=h[u],h[u]=cnt;
}void dfs(int x){
    dfn[x]=low[x]=++tot;
    s.push(x);is[x]=1;
    for(int i=h[x];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v])dfs(v),low[x]=min(low[x],low[v]);
        else if(is[v])low[x]=min(low[x],dfn[v]);
    }if(dfn[x]==low[x]){
        ans++;vec[ans].push_back(x);
        while(s.top()!=x){
            in[s.top()]=ans;
            is[s.top()]=0;
            vec[ans].push_back(s.top());
            s.pop();
        }s.pop();is[x]=0;in[x]=ans;
    }
}signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;cin>>u>>v;add(u,v);
    }for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
    cout<<ans<<'\n';
    for(int i=1;i<=ans;++i)sort(vec[i].begin(),vec[i].end());
    for(int i=1;i<=n;++i){
        if(f[in[i]])continue;
        f[in[i]]=1;
        for(int j=0;j<vec[in[i]].size();++j)
            cout<<vec[in[i]][j]<<' ';
        puts("");
    }
    return 0;
}