最近公共祖先LCA
如圖
LCA(4,5)=8
LCA(10,16)=10
LCA(7,3)=4
求LCA主要演算法有：RMQ,tarjan,倍增
RMQ
這種方法就是打表
O(n logn)預處理，O(1)回答
RMQ就是區間最值查詢，
首先通過dfs求出每個點的深度
顯然，兩個節點的LCA不僅是兩個節點的最近公共祖先，而且包括這兩個節點的最小子樹的根，即包括這兩個節點的最小子樹中的深度最小的節點，
現在，我們改一下dfs，變成歐拉序，
歐拉序，就是每次從x的父親進入節點x或者從子節點回溯到x都要把x這個編號扔到一個陣列的最后，
如上圖
歐拉序為：8 5 9 5 8 4 6 15 6 7 6 4 10 11 10 16 3 16 12 16 10 2 10 4 8 1 14 1 13 1 8
再注意到，一對點的 LCA 不僅是包括這兩個節點的最小子樹中的深度最小的節點，還是連接這對點的簡單路徑上深度最小的點，
而且從離開x到進入y的這段歐拉序必然包括所有這對點之間的簡單路徑上的所有點，所以我們考慮求得這段歐拉序中所包含的節點中的深度最小的點,即他們的LCA，
從x到y的這段歐拉序會包含這棵子樹中的其他節點，但是不會影響這個最淺點的求得，
顯然，x到y這段歐拉序是個連續區間，
現在我們考慮通過預處理來O(1)獲得這個最淺點，
這里有一個叫做ST表的東西，
代碼
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],ind,dfn[50005],dep[50005],lg[50005],f[50005][21];
void add(int u,int v){
cnt++;
ed[cnt].to=v;
ed[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int fa){
dfn[u]=++ind;
dep[u]=dep[fa]+1;
f[ind][0]=u;
for(int i=head[u];i;i=ed[i].next){
int v=ed[i].to;
if(v!=fa)dfs(v,u),f[++ind][0]=u;
}
}
void st(){
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)<=ind+1;i++){
int k=i+(1<<(j-1));
if(dep[f[i][j-1]]<dep[f[k][j-1]])f[i][j]=f[i][j-1];
else f[i][j]=f[k][j-1];
}
}
}
int rmq(int l,int r){
if(l>r)swap(l,r);
int k=lg[r-l+1];
if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]])return f[l][k];
else return f[r-(1<<k)+1][k];
}
int main(){
scanf("%d%d",&n,&q);
lg[0]=-1;
for(int i=1;i<=n;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,0);
st();
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
printf("%d\n",rmq(dfn[u],dfn[v]));
}
}
Tarjan
一種離線演算法，要用到并查集，
時間復雜度為O(n+q)，
Tarjan演算法基于dfs，在dfs的程序中，對于每個節點位置的詢問做出相應的回答，
dfs的程序中，當一棵子樹被搜索完成之后，就把他和他的父親合并成同一集合；在搜索當前子樹節點的詢問時，如果該詢問的另一個節點已經被訪問過，那么該編號的詢問是被標記了的，于是直接輸出當前狀態下，另一個節點所在的并查集的祖先；如果另一個節點還沒有被訪問過，那么就做下標記，繼續dfs，
如上圖
比如：8−1−14−13,此時已經完成了對子樹1的子樹14的dfs與合并，如果存在詢問(13,14)，則其LCA即find(14)，即1；如果還存在由節點13與已經完成搜索的子樹中的節點的詢問，那么處理完，然后合并子樹13的集合與其父親1當前的集合，回溯到子樹1，并深搜完所有1的其他未被搜索過的兒子，并完成子樹1中所有節點的合并，再往上回溯，對節點1進行類似的操作即可，
代碼
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[50005];
struct qedge{
int to,next,lca;
}qed[50005];
int n,q,u,v,cnt,qcnt,head[50005],qhead[50005],fa[50005];
void add(int u,int v){
cnt++;
ed[cnt].to=v;
ed[cnt].next=head[u];
head[u]=cnt;
}
void qadd(int u,int v){
qcnt++;
qed[qcnt].to=v;
qed[qcnt].next=qhead[u];
qhead[u]=qcnt;
}
int find(int x){
return fa[x]==x?x:find(fa[x]);
}
void dfs(int u,int pa){
fa[u]=u;
for(int i=head[u];i;i=ed[i].next){
int v=ed[i].to;
if(v!=pa){
dfs(v,u);
fa[v]=u;
}
}
for(int i=qhead[u];i;i=qed[i].next){
int v=qed[i].to;
if(v!=pa&&!qed[i].lca){
qed[i].lca=find(v);
if(i%2)qed[i+1].lca=qed[i].lca;
else qed[i-1].lca=qed[i].lca;
}
}
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
qadd(u,v),qadd(v,u);
}
dfs(1,0);
for(int i=1;i<=q;i++)printf("%d\n",qed[2*i].lca);
}
倍增
時間復雜度O((n+q)logn)
對于這個演算法，我們從最暴力的演算法開始：
①如果x和y深度不同，先把深度調淺，使他變得和深度小的那個一樣
②現在已經保證了x和y的深度一樣，所以我們只要把兩個一起一步一步往上移動，直到他們到達同一個節點，也就是他們的最近公共祖先了，
代碼
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],dep[10005],fa[10005];
void add(int u,int v){
cnt++;
ed[cnt].to=v;
ed[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int pa){
dep[u]=dep[pa]+1,fa[u]=pa;
for(int i=head[u];i;i=ed[i].next){
int v=ed[i].to;
if(v!=pa)dfs(v,u);
}
}
int lca(int u,int v){
if(u==v)return u;
if(dep[u]==dep[v])return lca(fa[u],fa[v]);
if(dep[u]>dep[v])return lca(fa[u],v);
if(dep[u]<dep[v])return lca(u,fa[v]);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,0);
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
}
但這樣一步一步往上移動太慢，我們可以做一個預處理：
設fi,j表示從結點i開始向上走2j步到達的點，所以fi,0=fa(i),fi,1=ff[0][0],0,$fi,j=ff[i][j-1],i-j$
還是那幅圖
f5,0=5
f7,1=4
f3,2=ff[3][2-1],2-1=f10,1=8
于是我們可以得出以下做法：
1.把x和y移到同一深度（設depx為節點x的深度），假設depx<depy，從大到小列舉k，如果depf[y][k]≠depx，那么y就往上跳，
2.如果x=y，那么顯然LCA就是fx,0，否則執行第3步，
3.在xx≠yy的情況下找到深度最小的xx和yy，
代碼
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],dep[50005],f[50005][20];
void add(int u,int v){
cnt++;
ed[cnt].to=v;
ed[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int fa){
f[u][0]=fa;
dep[u]=dep[fa]+1;
for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=ed[i].next){
int v=ed[i].to;
if(v!=fa)dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;i>=0;i--)if(dep[u]-(1<<i)>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,0);
for(int i=1;i<=q;i++){
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/77542.html
標籤：C++
上一篇：c++-字串和時間操作