MENU

LCA模板

2019-06-29 • 阅读: 21 • 图论—LCA常用模板阅读设置

Tarjan :

只能离线处理,时间复杂度 O(n+m)O(n+m)

int get(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = get(fa[x]);
}
void tarjan(int u)
{
	vis[u] = true;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to,w=edge[i].w;
		if (vis[v]) continue;
		dis[v] = dis[u] + w;
		tarjan(v);
		fa[v] = u;
	}
	for (int i = head1[u]; i != -1; i = query[i].next)
	{
		int v = query[i].v;
		if (!vis[v]) continue;
		int lca = get(v);//这个即是u和v的LCA
		ans[query[i].id] = dis[v] + dis[u] - 2*dis[lca];//这是两点间的最短距离
	}
}

树上倍增

可以O(nlogn)O(nlog_n) 预处理,然后O(logn)O(log_n) 查询

void bfs()//预处理,也可以dfs
{
	//fat[1][0] = 1;
	queue<int> q;
	q.push(1);
	dep[1] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if (dep[v]) continue;
			dep[v] = dep[u] + 1;
			fat[v][0] = u;
			for (int j = 1; j <= up; j++)
			{
				fat[v][j] = fat[fat[v][j - 1]][j - 1];
			}
			q.push(v);
		}
	}
}
int lca(int u, int v)
{
	if (dep[u] > dep[v]) swap(u, v);
	for (int j = up; j >= 0; j--)
	{
		if (dep[fat[v][j]] >= dep[u]) v = fat[v][j];
	}
	if (u == v) return u;
	for (int j = up; j >= 0; j--)
	{
		if (fat[v][j] !=fat[u][j]){
			v = fat[v][j];
			u = fat[u][j];
		}
	}
	return fat[v][0];
}

LCA转RMQ

首先对树进行深度优先遍历,得到欧拉序以及每个节点首次出现的位置,同时保存深度信息。

  • vs[i]vs[i] : 表示第ii次访问的节点的编号
  • dep[i]dep[i]: 表示第ii次访问时的深度
  • in[i]in[i] :节点ii首次出现在vsvs数组中的位置

询问uuvvLCALCA,先得到它们俩首次出现的位置区间内[in[u],in[v]][ in[u],in[v] ]深度最低的位置下标,记为pospos,则vs[pos]vs[pos]即是他俩的LCALCA。用STST表求解即可。

void dfs(int u,int d,int fa)
{
	in[u] = ++top;
	vs[top] = u;
	dep[top] = d;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to, w = edge[i].w;
		if (v==fa) continue;
		dis[v] = dis[u] + w;
		dfs(v, d + 1,u);
		vs[++top] = u;
		dep[top] = d;
	}
}
void RMQ()
{
	for (int i = 0; i <= top; i++)
		dp[i][0] = i;
	for (int j = 1; j <= up; j++)
	{
		for (int i = 1; (i+(1<<j)-1) <= top; i++)
		{
			int p1 = dp[i][j - 1], p2 = dp[i + (1 << (j - 1))][j - 1];
			if (dep[p1] <= dep[p2]){
				dp[i][j] = p1;
			}
			else{
				dp[i][j] = p2;
			}
		}
	}
}
int lca(int l,int r)
{
	if (l > r) swap(l, r);
	int k = log2(r - l + 1);
	int p1 = dp[l][k], p2 = dp[r - (1 << k) + 1][k];
	if (dep[p1] <= dep[p2]) return vs[p1];
	else return vs[p2];
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码