tarjan LCA算法和基于+-RMQ和欧拉序列的LCA算法

naturerun

264人浏览 · 2025-11-06 23:11:55

naturerun · 2025-11-06 23:11:55 发布

tarjan LCA算法讲解见Tarjan LCA
基于±RMQ和欧拉序列的LCA算法的思路是构建树的欧拉序列,树上两个节点的LCA就是欧拉序列对应区间内深度最小的节点,且欧拉序列上相邻两项的深度值的差要么为1，要么为-1，所以LCA的查询可以用±RMQ做到.以下代码简单起见没有使用±RMQ ±RMQ实现见
±RMQ

C++代码

#include <iostream>
#include <map>
#include <set>
using namespace std;
#include "strToTree.h"
#include "RMQ.h"


class UnionFindSet
{
public:
	UnionFindSet(size_t N) :_set(N, -1) {}
	long long findSet(long long n)
	{
		long long p = n;
		while (_set[p] >= 0)
		{
			p = _set[p];
		}
		return p;
	}

	long long unionSet(long long _left, long long _right)
	{
		long long left = findSet(_left);
		long long right = findSet(_right);
		if (_set[left] < _set[right])
		{
			_set[left] += _set[right];
			_set[right] = left;
			return left;
		}
		else
		{
			_set[right] += _set[left];
			_set[left] = right;
			return right;
		}

	}
private:
	vector<long long> _set;
};
void DFS(MultiTreeNode<char>* root, vector<NodeDepth> &Euler_Seq, vector<char> &node_seq, int &depth)
{
		++depth;
		node_seq.push_back(*(root->data_field));
		int depth_first_index = node_seq.size() - 1;
		Euler_Seq.push_back(NodeDepth(depth_first_index, depth));
		for (size_t i = 0; i < root->sub_node_ptr.size(); ++i)
		{
			if (root->sub_node_ptr[i] != nullptr)
			{
				DFS(root->sub_node_ptr[i], Euler_Seq, node_seq, depth);
				Euler_Seq.push_back(NodeDepth(depth_first_index, depth));
			}
		}
		--depth;
}

long long TarjanLCA(MultiTreeNode<char>* root, const vector<pair<long long, long long>>& question_relation, vector<bool> &visited, vector<char>& node_seq, long long & index, UnionFindSet &_set, vector<size_t> &ancestor)
{
	++index;
	long long cur_node_index = index;
	for (size_t i = 0; i < root->sub_node_ptr.size(); ++i)
	{
		if (root->sub_node_ptr[i] != nullptr)
		{
			long long temp = TarjanLCA(root->sub_node_ptr[i], question_relation, visited, node_seq, index, _set, ancestor);
			ancestor[_set.unionSet(cur_node_index, temp)] = cur_node_index;
		}
	}

	visited[cur_node_index] = true;
	for (size_t i = 0; i < question_relation.size(); ++i)
	{
		if (question_relation[i].first == cur_node_index)
		{
			if (visited[question_relation[i].second])
			{
				cout << *(root->data_field) << "和" << node_seq[question_relation[i].second] << "的LCA=" << node_seq[ancestor[_set.findSet(question_relation[i].second)]] << endl;
			}
		}
		else if (question_relation[i].second == cur_node_index)
		{
			if (visited[question_relation[i].first])
			{
				cout << *(root->data_field) << "和" << node_seq[question_relation[i].first] << "的LCA=" << node_seq[ancestor[_set.findSet(question_relation[i].first)]] << endl;
			}
		}
	}
	return cur_node_index;
}

int main()
{
	const size_t N = 7;  //N必须大于等于2，为树中节点数
	string tree = "a(b,c,d( , ,f(t,n, )))(";
	if (!inspectGenListExpr(tree, 3))
	{
		exit(-1);
	}

	vector<pair<long long, long long>> question_relation = { {2, 4}, {2, 6}, {3, 5}, {3, 6} };
	MultiTreeNode<char>* root = strGenToTree<char>(tree, 3);
	vector<NodeDepth> Euler_Seq;
	vector<char> node_seq;

	int depth = 0;
	DFS(root, Euler_Seq, node_seq, depth);

	vector<vector<NodeDepth>> d(Euler_Seq.size(), vector<NodeDepth>(Euler_Seq.size()));
	SparseTable(d, Euler_Seq);

	int left_question = 5;
	int right_question = 6;

	vector<vector<size_t>> dfs_index_to_eular_tour_index(N, vector<size_t>());
	for (size_t i = 0; i < Euler_Seq.size(); ++i)
	{
		if (dfs_index_to_eular_tour_index[Euler_Seq[i].depth_first_index].size() > 1)
		{
			dfs_index_to_eular_tour_index[Euler_Seq[i].depth_first_index].pop_back();
		}
		dfs_index_to_eular_tour_index[Euler_Seq[i].depth_first_index].push_back(i);
	}

	size_t left_first_appear = dfs_index_to_eular_tour_index[left_question][0];
	size_t right_first_appear = dfs_index_to_eular_tour_index[right_question][0];
	size_t left_last_appear;
	if (dfs_index_to_eular_tour_index[left_question].size() == 1)
	{
		left_last_appear = left_first_appear;
	}
	else
	{
		left_last_appear = dfs_index_to_eular_tour_index[left_question][1];
	}
	int LCA;
	if (left_last_appear < right_first_appear)
	{
		LCA = query(left_last_appear + 1, right_first_appear - 1, d).depth_first_index;
	}
	else
	{
		LCA = left_first_appear;
	}

	cout << node_seq[left_question] << "和"<< node_seq[right_question] << "的LCA=" << node_seq[LCA];
	cout << endl;

	long long index = -1;
	vector<bool> visited(node_seq.size(), false);
	UnionFindSet _set(node_seq.size());
	vector<size_t> ancestor(node_seq.size());
	TarjanLCA(root, question_relation, visited, node_seq, index, _set, ancestor);
	return 0;
}

strToTree.h内容

#pragma once
#include <vector>
#include <stack>
#include <string>
#include <cctype>

template <typename T>
struct MultiTreeNode
{
	T* data_field;
	vector<MultiTreeNode*> sub_node_ptr;
	MultiTreeNode(size_t n, T* d) :sub_node_ptr(n, nullptr), data_field(d) {}
	~MultiTreeNode() { delete data_field; }
};

template <typename T>
class Gennode
{
public:
	int numnode;
	MultiTreeNode<T>* ptr;
	Gennode(MultiTreeNode<T>* p) :ptr(p), numnode(-1) {}
};

bool inspectSubList(string::size_type &index, string& expr, const int &k)
{
	bool have_error = false;
	string::size_type sub_list = index;
	size_t sub_list_mem_count = 0;
	bool has_no_empty_mem = false;
	while (true)
	{
		++index;
		if (index == expr.size())
		{
			cout << "ERROR:下标为" << sub_list << "的子表达式不完整" << endl;
			return false;
		}

		if (!isalnum(expr[index]) && expr[index] != ' ')
		{
			cout << "ERROR:子表(位置" << sub_list << ")的第" << ++sub_list_mem_count << "个成员为非法字符" << endl;
			have_error = true;
		}

		++sub_list_mem_count;
		if (expr[index] != ' ')
		   has_no_empty_mem = true;
		++index;
		if (index == expr.size())
		{
			cout << "ERROR:子表(位置" << sub_list << ")缺少右括号" << endl;
			if (has_no_empty_mem == false)
			{
				cout << "ERROR:下标为" << sub_list << "的子表不能只包含空成员" << endl;
			}
			return false;
		}

		if (isalnum(expr[index - 1]))
		{
			if (expr[index] == '(')
			{
				if (!inspectSubList(index, expr, k))
				{
					if (index == expr.size())
					{
						cout << "ERROR:下标为" << sub_list << "的子表达式不完整" << endl;
						return false;
					}
					have_error = true;
				}

				++index;
				if (index == expr.size())
				{
					cout << "ERROR:子表(位置" << sub_list << ")缺少右括号" << endl;
					return false;
				}
			}
		}

		if (expr[index] != ',' && expr[index] != ')')
		{
			cout<<"ERROR:子表(位置" << sub_list << ")第"<< sub_list_mem_count << "个成员后存在非法字符" << endl;
			have_error = true;
		}
		else if (expr[index] == ')')
		{
			if (has_no_empty_mem == false)
			{
				cout << "ERROR:下标为" << sub_list << "的子表不能只包含空成员" << endl;
				have_error = true;
			}

			if (k != sub_list_mem_count)
			{
				cout<<"ERROR:下标为" << sub_list << "的子表成员数必须为" << k << endl;
				have_error = true;
			}
			return !have_error;
		}
	}
}

bool inspectGenListExpr(string& expr, const int &k)
{
	if (expr.size() < 3)
	{
		cout << "ERROR:错误的最外层广义表格式" << endl;
		return false;
	}

	if (expr.size() == 3)
	{
		if (!(isalnum(expr[0]) && expr[1] == '(' && expr[2] == ')'))
		{
			cout << "ERROR:错误的最外层广义表格式" << endl;
			return false;
		}
		return true;
	}
	else
	{
		if (isalnum(expr[0]) && expr[1] == '(')
		{
			string::size_type index = 1;
			bool r = inspectSubList(index, expr, k);
			if (r)
			{
				++index;
				if (index != expr.size())
				{
					cout << "ERROR:完整的广义表表达式后存在意外字符" << endl;
					return false;
				}
			}
			return r;
		}
		cout << "ERROR:错误的最外层广义表格式" << endl;
		return false;
	}
}

template <typename T>
MultiTreeNode<T>* strGenToTree(string& gen, int k)
{
	MultiTreeNode<T>* ptr = nullptr; stack<Gennode<T>> work_stack;
	char cur_char = '\0';
	auto test = gen.cbegin();
	++test;
	for (auto i = gen.cbegin(); i != gen.cend(); ++i) //从左至右扫描广义表
	{
		if (*i == '(')  //左括号
		{
			if (i == test)  //第一个左括号
			{
				ptr = new MultiTreeNode<T>(k, new T(cur_char));   //新建根节点入栈
				Gennode<T> temp(ptr);
				work_stack.push(temp);
			}
			else    //子表左括号
			{
				MultiTreeNode<T>* temp = new MultiTreeNode<T>(k, new T(cur_char));    //新建非叶子节点
				ptr->sub_node_ptr[++work_stack.top().numnode] = temp;   //连接至父节点
				ptr = temp;
				Gennode<T> temp2(ptr);  //ptr指向新建节点并入栈
				work_stack.push(temp2);
			}
			cur_char = '\0';
		}
		else
		{
			if (*i == ')')  //右括号，父节点在本层子节点建立并链接完毕
			{
				if (cur_char != '\0')
				{
					MultiTreeNode<T>* temp = new MultiTreeNode<T>(k, new T(cur_char));   //建立与原子数据对应子节点
					ptr->sub_node_ptr[++work_stack.top().numnode] = temp;   //链接至父节点
					cur_char = '\0';
				}
				work_stack.pop();   //直接出栈
				if (work_stack.size() != 0)
					ptr = work_stack.top().ptr; //ptr回溯至父节点
			}
			else
			{
				if (*i != ',' && *i != ' ')   //原子数据
				{
					cur_char = *i;
				}
				else if (*i == ',')
				{
					if (cur_char != '\0')
					{
						MultiTreeNode<T>* temp = new MultiTreeNode<T>(k, new T(cur_char));   //建立与原子数据对应子节点
						ptr->sub_node_ptr[++work_stack.top().numnode] = temp;   //链接至父节点
						cur_char = '\0';
					}
				}
				else if (*i == ' ')
				{
					++work_stack.top().numnode;
				}
			}
		}
	}//扫描完后ptr即为k叉树根节点指针
	return ptr;
}

RMQ.h内容

#pragma once
#include <vector>
#include <algorithm>
using std::vector;
using std::min;

struct NodeDepth
{
	int depth_first_index;
	int depth;
	NodeDepth(int d, int depth) :depth_first_index(d), depth(depth) {}
	NodeDepth() = default;
};

void SparseTable(vector<vector<NodeDepth>>& d, vector<NodeDepth>& seq)
{
	for (size_t i = 0; i < seq.size(); ++i)
	{
		d[i][0] = seq[i];
	}

	for (size_t i = 1; (1 << i) <= seq.size(); ++i)
	{
		for (size_t j = 0; j <= seq.size() - (1 << i); ++j)
		{
			if (d[j][i - 1].depth < d[j + (1 << i - 1)][i - 1].depth)
			{
				d[j][i] = d[j][i - 1];
			}
			else
			{
				d[j][i] = d[j + (1 << i - 1)][i - 1];
			}
		}
	}
}

NodeDepth query(size_t i, size_t j, vector<vector<NodeDepth>>& d)
{
	size_t k = 0;
	size_t l = j - i + 1;
	while (1 << k <= l)
	{
		++k;
	}
	--k;
	if (d[i][k].depth < d[j - (1 << k) + 1][k].depth)
	{
		return d[i][k];
	}
	else
	{
		return d[j - (1 << k) + 1][k];
	}
}