D09 倍增算法 P3379【模板】最近公共祖先(LCA)_哔哩哔哩_bilibili
P3379 【模板】最近公共祖先(LCA) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
三种算法比较
倍增法
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
int dep[maxn],fa[maxn][64]; //dep统计深度,fa[i][j]向上跳j步的位置,倍增着跳 void dfs(int u,int father){ dep[u]=dep[father]+1; for (int i=1;i<64;i++){ //原理结合上图理解 fa[u][i]=fa[fa[u][i-1]][i-1]; } for (int v=head[u];~v;v=edge[v].next){ if (edge[v].v!=father){ dfs (edge[v].v,u); } } } int lca(int u,int v){ if (dep[u]<dep[v]){ //使得u的深度更深 swap(u,v); } for (int i=63;i>=0;i--){ //跳到同一层 //如果 u跳到第i步的祖先节点的深度仍然比v的深度大,则u继续向上跳 //如果深度比较小,证明跳的太远,不操作,下次近一些 //直到跳到同意深度 if (dep[fa[u][i]]>=dep[v]){ u=fa[u][i]; } } if(u==v){ //如果相等则最近公共祖先找到了 return v; } for (int i=62;i>=0;i--){ //一起向上跳相同远,如果位置相同,则找到公共祖先 //但不见得是最近公共祖先 ,那就跳近点试试 //如果不相等,那最近公共祖先一定还在上面接着跳。 //直到跳到最新公共祖先的子节点上 if (fa[u][i]!=fa[v][i]){ u=fa[u][i],v=fa[v][i]; } } //此时u的父节点就是最近公共祖先 return fa[u][0]; }
Tarjan算法:并查集原理
123456789101112131415161718192021222324252627282930313233343536373839
vector <pair<int,int>> query[maxn]; //query[a]<paor<b,t>>表示第t次询问,询问a,b的最近公共祖先 int fa[maxn],ans[maxn]; bool vis[maxn]; int find (int u){ int a=u; while (a!=fa[a]){ a=fa[a]; } while (a!=fa[u]){ int t=fa[u]; fa[u]=a; u=t; } return a; } void tarjan(int u){ //注意询问要双向存储 vis[u]=true; for (int v=head[u];~v;v=edge[v].next){ //用递归自下向上使用并查集维护他们的公共祖先,当a,b第一次 //都出现在并查集上时,就找到了他们的最近公共祖先 if (!vis[edge[v].v]){ tarjan(edge[v].v); fa[edge[v].v]=u; } } for (auto q : query[u]){ int v=q.first,i=q.second; if (vis[v]){ //因为不知道a,b谁后进入并查集,所以询问要双向存储。 ans[i]=find[v]; } } }
树链刨分
1234567891011121314151617181920212223242526272829303132333435363738394041424344
int fa[maxn],dep[maxn],son[maxn],sz[maxn]; int top[maxn]; void dfs1(int u,int father)//搞 fa,dep,son,即父节点,深度,重儿子 { fa[u]=father; dep[u]=dep[father]+1; sz[u]=1; for (int v=head[u];~v;v=edge[v].next){ if (edge[v].v!=father){ dfs1(edge[v].v,u); sz[u]+=sz[edge[v].v]; if (sz[son[u]]<sz[edge[v].v]){ son[u]=edge[v].v; } } } } void dfs2(int u,int t){//搞 top 即重链的头 top[u]=t; if (!son[u]){ return ; //无重儿子返回 } dfs2(son[u],t); for (int v=head[u];~v;v=edge[v].v){ if (edge[v].v==fa[u]||edge[v].v==son[u]){ contime ; } dfs(edge[v].v,edge[v].v); } } int lca(int u,int v){ while (top[u]!=top[v]){ //不在一条重链上,则链头深的向上跳, if (dep[top[u]]<dep[top[v]]) { swap(u,v); } //跳到另一条重链上,即链头的父节点 u=fa[top[u]]; } //若在同一条重链上,则深度更浅的就是最近公共祖先 return dep[u]<dep[v]?u:v; }