LCA算法合集

这两天看了看“最近公共祖先”(lowest common ancestors, LCA)
先说什么是LCA
好吧,顾名思义,就是,两个节点的深度最大的公共祖先
比如,上图中 4,7 的 LCA就是 2 , 3,6 的则是 3;
那么怎么做呢?

1.朴素算法(在线)
由较深的节点一直向上走,直到与另一个节点到达同一深度,接着两个节点一起向根走,直到达到统一节点,这个节点就是他们的LCA。
复杂度(对于每次询问):最坏 O(n),平均 O(log n)
代码:

[code language=”cpp”]
//这就不贴了吧
[/code]


2.Tarjan(离线)
首先把所有询问读入并存储,每次DFS都把儿子们所在的集合连接到当前节点上,再大力查询一波,如果与前节点与有查询关系的节点已经访问,那么他们的LCA既是当前节点的祖先(讲得不清楚,意会一下)
复杂度(处理+查询):O(n + q)
代码:

[code]
function TarjanOLCA(u)
MakeSet(u);
u.ancestor := u;
for each v in u.children do
TarjanOLCA(v);
Union(u,v);
Find(u).ancestor := u;
u.color := black;
for each v such that {u,v} in P do
if< v.color == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + ".";
[/code]

由于上述代码使用了 “set” 这个集合操作,而我们绝对没有必要用STL的std::set(又慢又“过于强大”)。所以我们要使用并查集。
下面是我自己的(虽然拖进提交框就能跑,但还是别按Ctrl-C了吧)

[code language=”cpp”]
#include
#include
using namespace std;
const int N = 500010, M = 1000010;
int top[N], cnt = 0, fa[N], ans[N], E = 0, succ[M], nxt[M], con[M], to[M], fst[N], num[M];
bool vis[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}</static inline void add(int u, int v)
{
    to[++E] = v;
    nxt[E] = fst[u];
    fst[u] = E;
}
static inline void addquery(int u, int v, int i)
{
    num[++cnt] = i;
    con[cnt] = v;
    succ[cnt] = top[u];
    top[u] = cnt;
}
void Tarjan(int now)
{
    vis[now] = true;
    for(int i = fst[now]; i !=-1; i = nxt[i])
    {
        int aim = to[i];
        if(vis[aim])continue;
        Tarjan(aim);
        fa[find(aim)] = find(now);
    }
    int temp;
    for(int i = top[now]; i !=-1; i = succ[i])
    {
        int v = con[i];
        temp = num[i];
        if(vis[v]) ans[temp] =find(v);
    }
}
int main()
{
    int n, m, s, u, v;
    scanf("%d%d%d", &n, &m, &s);
    memset(fst, -1, sizeof(fst));
    memset(top, -1, sizeof(top));
    memset(vis, 0, sizeof(vis));
    for(int i =1; i <= n; i++) fa[i] = i;
    for(int i =1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for(int i =1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        addquery(u, v, i), addquery(v, u, i);
    }
    Tarjan(s);
    for(int i =1; i <= m; i++)printf("%d\n", ans[i]);
    return0;
}
[/code]


3.欧拉序+RMQ

4.倍增(在线)
考虑对朴素算法进行优化:向上“跳跃”由单步改为 2i 步,不断由大到小地调整,便可以得到正解。
复杂度: O(n) – O(q log n)
代码:

[code language=”cpp”]
#include
#include
#include
#include
#define log2(i) ((int)((double)log(i) / (double)log(2)))
const int N = 5e5 + 10;
using namespace std;

int n, p[N][28], fst[N], nxt[2 * N], to[2 * N], deep[N], E = 0;

inline void add(int b, int e) {to[++E] = e; nxt[E] = fst[b]; fst[b] = E;}

int lca(int a, int b)
{
if (deep[a] > deep[b]) swap(a, b);
int dh = deep[b] – deep[a];
for (int i = 0; (1 << i) <= dh; i++) if (1 <= 0; i–) if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
a = p[a][0];
}
return a;
}

void dfs(int now)
{
for (int i = fst[now]; i != -1; i = nxt[i]) if (to[i] != p[now][0])
{
deep[to[i]] = deep[now] + 1;
p[to[i]][0] = now;
dfs(to[i]);
}
}

int main()
{
int m, s, u, v;
scanf(“%d%d%d”, &n, &m, &s);
memset(fst, -1, sizeof(fst));
for (int i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
deep[s] = 0;
dfs(s);
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i <= n; i++)
p[i][j] = p[p[i][j – 1]][j – 1];
int x, y;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
[/code]


5.树链剖分(在线)

不会啊QAQ

“LCA算法合集”的3个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注