欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LCA 离线Tarjan算法 配题(HDU 4547)

程序员文章站 2022-05-27 16:17:25
...

LCA 在线算法是将问题转化为序列极值问题,使用动态规划的方式 进行求解,而离线LCA算法,表示在接收到所有查询的情况下,对所有查询同时进行处理。

LCA离线Tarjan算法:

思想:当一个祖先的一个子树被遍历完成之后进行回溯,并且告诉孩子的祖先是谁(注意顺序,先回溯,再去告诉孩子自己的组向,此处使用并查集进行操作),之后祖先在遍历其它子树的时候,如果在被访问过的节点中有和当前节点是查询的一对数据时,那么已经被访问过的节点的祖先就是这两个点的公共祖先。

配题:HDU 4547

思想:这个题目我用在线LCA疯狂WA,不知道为啥子。如果是离线算法一边就过了,这里注意要初始化结果数组res,因为有的情况下,结果应该是0,比如:N=1的时候,结果是0,但是如果不初始化res,那么你的lca_dfs过程根本就不回去修改res数组,但是其实是有输出的。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
using namespace std;
const int maxn = 100000 + 5;
struct NODE
{
	int v;
	int q_id;
	bool dir_mark; 
};
int N, M;
int cnt, tot;
int res[maxn];
int father[maxn];
int depth[maxn];
bool vis[maxn];
bool indegree[maxn];
vector<int>graph[maxn];
vector<NODE>q_graph[maxn];
map<string, int>mymap;
void init()
{
	cnt = 0;
	tot = 0;
	mymap.clear();
	memset(vis, false, sizeof(vis));
	memset(indegree, false, sizeof(indegree));
	memset(res, 0, sizeof(res));
	for (int i = 0; i <= N; i++)
	{
		graph[i].clear();
		q_graph[i].clear();
	}
	for (int i = 1; i <= N; i++)
	{
		father[i] = i;
	}
}

int ufs_find(int x)
{
	if (x != father[x])
	{
		father[x] = ufs_find(father[x]);
	}
	return father[x];
}

void ufs_union(int x, int y)
{
	x = ufs_find(father[x]);
	y = ufs_find(father[y]);
	if (x == y)
	{
		return;
	}
	father[y] = x;
}

void lca_dfs(int cur_node, int deep)
{
	vis[cur_node] = true;
	depth[cur_node] = deep;
	
	for (int i = 0; i < graph[cur_node].size(); i++)
	{
		int next_node = graph[cur_node][i];
		if (vis[next_node]) continue;
		lca_dfs(next_node, deep+1);
		ufs_union(cur_node, next_node); 
	}
	
	for (int i = 0; i < q_graph[cur_node].size(); i++)
	{
		int next_node = q_graph[cur_node][i].v;
		int id = q_graph[cur_node][i].q_id;
		bool mark = q_graph[cur_node][i].dir_mark;
		if (!vis[next_node]) continue;
		
		int lca_id = ufs_find(father[next_node]);
		if (mark) // cur_node -> next_node;
		{
			res[id] = depth[cur_node] - depth[lca_id] + (lca_id != next_node);
		}
		else // next_node -> cur_node;
		{
			res[id] = depth[next_node] - depth[lca_id] + (lca_id != cur_node);
		}
	}
}

int main()
{
	int T;
	cin>> T;
	while (T--)
	{
		int root;
		cin>> N>> M;
		init();
		for (int i = 1; i <= N-1; i++)
		{
			char a[45], b[45];
			scanf("%s %s", a, b);
			if (!mymap[a]) mymap[a] = ++cnt;
			if (!mymap[b]) mymap[b] = ++cnt;
			graph[mymap[b]].push_back(mymap[a]);
			indegree[mymap[a]] = true;
		}
		
		for (int i = 1; i <= N; i++)
		{
			if (indegree[i] == false)
			{
				root = i;
				break;
			}
		}
		
		for (int i = 1; i <= M; i++)
		{
			char a[45], b[45];
			scanf("%s %s", a, b);
			int u = mymap[a];
			int v = mymap[b];
			struct NODE node;
			node.v = v;
			node.q_id = i;
			node.dir_mark = true;
			q_graph[u].push_back(node);
			node.v = u;
			node.dir_mark = false;
			q_graph[v].push_back(node);
		}
		
		lca_dfs(root, 1);
		
		for (int i = 1; i <= M; i++)
		{
			cout<< res[i]<< endl;
		}
	}
	return 0;
}