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;
}
上一篇: 前端工具使用的一些坑
下一篇: 一些前端用到的css以及js等相关的资源