首页 > 代码库 > POJ 1330 Nearest Common Ancestors LCA题解
POJ 1330 Nearest Common Ancestors LCA题解
本题是一个多叉树,然后求两点的最近公共单亲节点。
就是典型的LCA问题。这是一个很多解法的,而且被研究的很透彻的问题。
原始的解法:从根节点往下搜索,若果搜索到两个节点分别在一个节点的两边,那么这个点就是最近公共单亲节点了。
Trajan离线算法:首次找到两个节点的时候,如果记录了他们的最低单亲节点,那么答案就是这个最低的单亲节点了。
问题是如何有效记录这个最低单亲节点,并有效根据遍历的情况更新,这就是利用Union Find(并查集)记录已经找到的节点,并及时更新最新访问的节点的当前最低单亲节点。
就是并查集的灵活运用啦,如果学会了并查集那么学这个算法是不难的了。
下面是简单思路差不多是暴力法的解法,不过其实相对本题来说就是一次查询,故此这个也是不错的方法,而且平均时间效率不过O(lgn),应该是很快的了。
不过有思想和这个差不多的,但是更加省内存的方法,就是从需要查找的节点往单亲节点查找,那么速度是一样的,不过省内存,因为只需要记录一个父母节点就可以了,而且程序会简洁点。
int const MAX_N = 10001; struct Node { bool notRoot; vector<int> children; }; Node Tree[MAX_N]; int N; int find(int r, int lNode, int rNode) { if (!r) return 0; if (r == lNode) return r; if (r == rNode) return r; vector<int> found; for (int i = 0; i < (int)Tree[r].children.size(); i++) { found.push_back(find(Tree[r].children[i], lNode, rNode)); } int u = 0, v = 0; for (int i = 0; i < (int)found.size(); i++) { if (found[i] != 0) { if (u) v = found[i]; else u = found[i]; } } if (v) return r; return u; } void solve() { scanf("%d", &N); memset(Tree, 0, sizeof(Tree)); int u, v; for (int i = 1; i < N; i++) { scanf("%d %d", &u, &v); Tree[u].children.push_back(v); Tree[v].notRoot = 1; } int root = 0; for (int i = 1; i <= N; i++) { if (!Tree[i].notRoot) { root = i; break; } } scanf("%d %d", &u, &v); int r = find(root, u, v); printf("%d\n", r);//if (lin && rin) 必然是存在点,故此无需判断 } int main() { int T; scanf("%d", &T); while (T--) { solve(); } return 0; }
下面是Tarjan离线算法,效率应该和上面是一样的,多次查询的时候就能提高效率。不过实际运行比上面快。
#include <stdio.h> #include <string.h> #include <vector> using std::vector; int const MAX_N = 10001; struct Node { bool notRoot; bool vis; vector<int> children; }; Node Tree[MAX_N]; int N; int u, v; int parent[MAX_N]; inline int find(int x) { if (!parent[x]) return x; return parent[x] = find(parent[x]); } inline void unionTwo(int p, int x) { p = find(p); x = find(x); if (p == x) return ; parent[x] = p; } bool LCATarjan(int root) { Tree[root].vis = true; if (root == u && Tree[v].vis == true) { printf("%d\n", find(v)); return true; } if (root == v && Tree[u].vis == true) { printf("%d\n", find(u)); return true; } for (int i = 0; i < (int)Tree[root].children.size(); i++) { if (LCATarjan(Tree[root].children[i])) return true; unionTwo(root, Tree[root].children[i]); } return false; } void solve() { scanf("%d", &N); memset(Tree, 0, sizeof(Tree)); memset(parent, 0, sizeof(parent)); for (int i = 1; i < N; i++) { scanf("%d %d", &u, &v); Tree[u].children.push_back(v); Tree[v].notRoot = 1; } int root = 0; for (int i = 1; i <= N; i++) { if (!Tree[i].notRoot) { root = i; break; } } scanf("%d %d", &u, &v); LCATarjan(root); } int main() { int T; scanf("%d", &T); while (T--) { solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。