北京门户网站网址,湖北智能网站建设推荐,昆明专业网站建设公司,WordPress工具主题LCA#xff08;least common ancestors#xff09;最近公共祖先 指的就是对于一棵有根树#xff0c;若结点z既是x的祖先#xff0c;也是y的祖先#xff08;不要告诉我你不知道什么是祖先#xff09;#xff0c;那么z就是结点x和y的最近公共祖先。 定义到此。 那么怎么求…LCAleast common ancestors最近公共祖先 指的就是对于一棵有根树若结点z既是x的祖先也是y的祖先不要告诉我你不知道什么是祖先那么z就是结点x和y的最近公共祖先。 定义到此。 那么怎么求LCA 对于朴素思想就是我要一步一步往上爬。。一步一步走。先把结点x和y整到同一深度然后再一次一个深度的往上查直到祖先一样才break明显是个while 但是一步一步实在是太慢了所以不能脚踏实地地走 那么考虑跳着走 跳着走的条件就是要满足一步步数尽可能多并且不跳过了。当然你跳过了在一步一步往下找也行啊QWQ 于是在满足这两个条件的情况下我们有了LCA算法 一步条2的n次方。 对于每一步跳跃我们要预处理一个二维数组ffatherf[x][i]表示对于当前的x结点往上跳2^i个祖先特别的像数学中的f[x][0]就是x的一代祖先。于是我们要用一个dfs预处理来解决这个f数组。后面我们会提到 处理完f数组那就很简单了。 输入x和y表示要求结点x和结点y的LCA那么我们开始求LCA 对于x和y在不同高度我们先把他们拉到一个高度同样不能一步一步走也要用到f数组。 这里我们要提前了解到一个定理对于任意一个非零整数我们都可以将他用2的次幂表示出来。也就是such as 112^32^12^0。这倒也不用证明就像每个数都可以用二进制表示一样。 接着讲在把x和y弄到同一高度时我们要先做的是设x的深度dep要比y的深度dep要大如果dep[y]dep[x],那么把他们交换。原因是如果不交换那么我们需要判断两种情况用两个if以及几乎相同的代码。。乱七八糟还占内存 然后用一个判断 if(dep[f[x][i]]dep[y])xf[x][i];此时x深度大于y在这里用外层for循环来枚举i但是i一定要从大到小。为什么 安利一个故事其实也不算一个玻璃瓶装了几块石头满到瓶口。满了吗没有。又装了一些沙子满到瓶口。满了吗没有。最后又装满了水满到瓶口。终于满了。 那么类比于x和y的深度的距离这个瓶子的容积也是同样道理。从2的尽可能大的次幂去找一旦能找到能接近他们的i就更新dep[x]直到相等。类似于无限逼近最后值相等的过程。如果i相等了就说明他们的深度已经在同一层了。 与倍增到同一深度的过程相比倍增找公共祖先也是类似的但是有一点不同就是你不知道什么时候找到他们的公共祖先因此就没有查找的上限那么就让他们尽可能接近。因此条件改成了这个 if(f[x][i]!f[y][i]) { xf[x][i];yf[y][i]; } 在执行完这个语句后我们成功让x和y变成了某一节点z的左右儿子 因为左右儿子是最接近但是又不相等的。 那么我们随便取其中一个找爸爸就找到了LCA。 啊。。。。。。喘口气 AC代码 有关链式存图不懂的的点这里。 #includecstdio
#includeiostream
using namespace std;
int n,m,s,num0,head[1000001],dep[1000001],f[1000001][23];
int a1,a2;
struct edg{int next,to;
}edge[1000001];
void edge_add(int u,int v)//链式前向星存图
{num;edge[num].nexthead[u];edge[num].tov;head[u]num;edge[num].nexthead[v];edge[num].tou;head[v]num;
}
void dfs(int u,int father)//对应深搜预处理f数组
{dep[u]dep[father]1;for(int i1;(1i)dep[u];i){f[u][i]f[f[u][i-1]][i-1];}for(int ihead[u];i;iedge[i].next){int vedge[i].to;if(vfather)continue;//双向图需要判断是不是父亲节点 f[v][0]u;dfs(v,u);}
}
int lca(int x,int y)
{if(dep[x]dep[y])swap(x,y);for(int i20;i0;i--)//从大到小枚举使x和y到了同一层 {if(dep[f[x][i]]dep[y])xf[x][i];if(xy)return x;}for(int i20;i0;i--)//从大到小枚举 {if(f[x][i]!f[y][i])//尽可能接近 {xf[x][i];yf[y][i];} } return f[x][0];//随便找一个**输出
}
int main(){scanf(%d%d%d,n,m,s);for(int i1;in;i){scanf(%d,a1);scanf(%d,a2);edge_add(a1,a2);//链式存边 }dfs(s,0);for(int i1;im;i){scanf(%d %d,a1,a2);printf(%d\n,lca(a1,a2));//求两个节点的LCA }
} 完结。。 转载于:https://www.cnblogs.com/lbssxz/p/11114819.html
