天河门户网站建设,广州品牌网站开发,建筑设计网站大全网站,网站建设工资一月多少钱目录 1 介绍2 训练 1 介绍
本博客用来记录对于有根图中#xff0c;求最近公共祖先的题目。
求解方法#xff1a;
向上标记法。每次求两个结点的最近公共祖先的时间复杂度是O(N)。由于时间复杂度较高#xff0c;通常不用。倍增法。
倍增法重要思路#xff1… 目录 1 介绍2 训练 1 介绍
本博客用来记录对于有根图中求最近公共祖先的题目。
求解方法
向上标记法。每次求两个结点的最近公共祖先的时间复杂度是O(N)。由于时间复杂度较高通常不用。倍增法。
倍增法重要思路预处理出两个数组fa[i][j]和depth[i]。其中fa[i][j]表示从i开始向上走2^j步所能走到的结点。0jlogn。depth[i]表示深度为到根结点的距离再加上1。
哨兵如果从i开始跳2^j步会跳过根结点那么fa[i][j] 0depth[0] 0。
倍增法重要步骤
先将两个点跳到同一层。让两个点同时往上跳一直跳到它们的最近公共祖先的下一层。
倍增法的时间复杂度分析预处理的时间复杂度为O(NlogN)查询的时间复杂度为O(logN)。
2 训练
题目11172祖孙询问
C代码如下
#include iostream
#include cstring
#include algorithm
#include queue
#include unordered_mapusing namespace std;const int N 40010;
int n, m;
int depth[N], fa[N][16];
int ancestor;
unordered_mapint, vectorint g;void bfs(int root) {memset(depth, 0x3f, sizeof depth);depth[0] 0;depth[root] 1; queueint q;q.push(root);while (!q.empty()) {int a q.front();q.pop();for (auto b : g[a]) {if (depth[b] depth[a] 1) {depth[b] depth[a] 1;q.push(b);fa[b][0] a;for (int k 1; k 15; k) {fa[b][k] fa[fa[b][k-1]][k-1];}}}}return;
}int lca(int a, int b) {//倍增法if (depth[a] depth[b]) swap(a, b);for (int k 15; k 0; --k) {if (depth[fa[a][k]] depth[b]) {a fa[a][k];}}if (a b) return a;for (int k 15; k 0; --k) {if (fa[a][k] ! fa[b][k]) {a fa[a][k];b fa[b][k];}}return fa[a][0];
}int main() {cin n;int a, b;for (int i 0; i n; i) {cin a b;if (b -1) {ancestor a;} else {g[a].emplace_back(b);g[b].emplace_back(a); }}cin m;vectorpairint,int queries;for (int i 0; i m; i) {cin a b;queries.emplace_back(a,b);}//从根结点开始遍历bfs(ancestor);for (auto [a, b] : queries) {int x lca(a, b);if (a x) {puts(1);} else if (b x) {puts(2);} else {puts(0);}}return 0;
}题目21171距离
C代码如下
