图论 |
您所在的位置：网站首页 › 图论有啥用 › 图论 |
图论
|
最近公共祖先
（Least Common Ancestors，LCA）问题：给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 Tarjan算法解决 LCA虽然也叫Tarjan算法，但是并不是求强连通分量的Tarjan算法。Tarjan很厉害，他发明了很多算法。。。 Tarjan算法解决LCA问题，基于深度优先搜索。我们能想到，对于一棵树的根节点执行深度优先搜索，形成的搜索树，和这棵树本身的形态实际上没有什么区别。而深度优先搜索的顺序是：到达一个结点后，依次按编号从小到大访问这个结点的每个子树，最后回到该节点。而这个结点就是他自己的不同子树上的点的最近公共祖先。假设（u，v）是需要求最近公共祖先的结点对，那么： 深搜回溯到结点u（或v，二者地位对称，这里以u为例）时，如果v结点还没有被访问过，那么此时还不能确定（u，v）的最近公共祖先。如果回溯到 u 时， v 已经被访问过了，那么两个结点的最近公共祖先也一定被回溯过至少一次了（因为（u，v）分别在不同子树，而最近公共祖先是他们共同的根节点），所以我们只需要在深度优先搜索的过程中，记录一个结点的 “向上回溯的位置”，可以理解成父亲结点。就能求出LCA。 算法描述 将每个结点的父节点初始化为自身 father[i] = i从根节点开始深度优先搜索，将访问过的每个结点标记为已访问。一个结点 u 结束搜索时（回溯时），更新该结点的父节点为其在搜索树中的父节点，并检查所有与结点 u 有关的询问（u，v），如果 v 已经被访问过了，那么（u，v）的最近公共祖先就是 v 回溯到的最早的父节点 find(v)。 void Tarjan_LCA(int u) { vis[u] = 1; //标记已访问 for(int i=heade[u];i;i=edge[i].next) { int v = edge[i].to; if(vis[v]==0) { Tarjan_LCA(v); father[v] = u; //更新父节点 } } for(int i=headq[u];i;i=ask[i].next) //检查和结点u有关的询问，询问也用邻接表存储 { int v = ask[i].to; if(vis[v]==1&&!ask[i].done) //done 记录问题是否已经解决 { ans[ask[i].index] = find(v); //离线算法，得到答案的次序可能和题目输入次序不一致 //所以直接把答案写入应该写入的地方 ask[i].done = 1; ask[ask[i].same].done = 1; } } }Tarjan解决LCA问题的算法是离线算法，每个结点和每个询问都要访问一次，因此时间复杂度是 O(n+q)， q是询问数。 ST表解决LCA问题LCA可以根据 dfs序转化为RMQ问题，然后用ST表来求解。 首先定义三个数组： time[i]，表示dfs访问的第 i 个结点。deep[i]，表示 time[i] 的深度。first[i]，表示 time[i]第一次出现的下标。如果我们要求（u，v）的LCA，如果 first[u] = a，first[v] = b，那么根据dfs的性质可知，LCA就是 [a，b] 这个区间里深度最小的点。 ST表的预处理时间复杂度为， O(nlogn) 查询时间复杂度为 O(1)。 void dfs(int u, int d) //dfs处理三个数组 { first[u] = ++cnt; //第一次出现的下标 time[cnt] = u; //ver[i] dfs访问的第i个结点 deep[cnt] = d; //深度 for(int i=head[u];i;i=edge[i].next) { int v = edge[i].to; if(!first[v]) { dfs(v, dep+1); time[++tot] = u; deep[tot] = d; } } } 倍增求LCA我们可以想到，求LCA有一个朴素的做法，如果（u，v）两个结点的深度不同，我们假设 deep[u] > deep[v]，我们先让 u 向上找 v ，直到deep[u] == deep[v] ，然后再每次让 u 和 v 向上走一层，直到两个结点重合，这个结点就是（u，v）的LCA。但是这样一层一层找太慢了。 我们直到一个数字可以表示成若干个 2 的幂次的和。例如25=2^ 4+2^ 3+2 ^0 ，这样我们可以把要向上找的步数拆成 2 的幂次。用这样倍增的思想来加速算法。 预处理首先我们需要预处理出一个数组：fa[i][j]，表示结点 i 向上走 2^ j 步的祖先结点。这个可以由，结点向上走 2^ (j-1) 步的结点，再向上走 2^ (j-1) 步转移得到。 转移方程：fa[i][j] = fa[fa[i][j-1]][j-1] 预处理函数： void get_fa(int u,int father) { deep[u] = deep[father]+1; fa[u][0] = father; for(int i=1;i=deep[y]) x = fa[x][i]; } if(x==y) return y; //x==y 说明x和y在一条链上 for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; //此时x的父节点就是LCA } |
【本文地址】