LCA之离线Tarjan算法
原文链接 https://hsfzxjy.github.io/2014-11-02-lca-Tarjan/
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。
真是巧妙的算法!
比起树上倍增,Tarjan算法实现起来更为简单,一个DFS加并查集即可。缺点便是:需要先把所有的查询都读进来,并且要储存结果。复杂度为O(n+q)。
Code
var
sets: array [1..100] of longint;
visited: array [1..100] of Boolean;
a: array [1..100, 1..100] of Boolean;
questions: array [1..1000] of record
x, y: longint;
ans: longint;
end;
qn, n, i, m, x, y, root: longint;
function find(x: longint): longint;
begin
if x = sets[x] then exit(x);
sets[x] := find(sets[x]);
exit(sets[x]);
end;
procedure dfs(x: longint);
var
i: longint;
begin
visited[x] := true;
//对于两个节点都已访问到的询问,其结果已经出来了
for i := 1 to qn do
begin
if visited[questions[i].x] and visited[questions[i].y] then
if questions[i].x = x then
questions[i].ans := find(questions[i].y)
else if questions[i].y = x then
questions[i].ans := find(questions[i].x);
end;
for i := 1 to n do
begin
if not a[i, x] or visited[i] then continue;
dfs(i);
sets[find(i)] := x;
end;
end;
begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);
read(n, m);
for i := 1 to n do
sets[i] := i;
for i := 1 to m do
begin
read(x, y);
a[x, y] := true;
a[y, x] := True;
end;
read(root);
qn := 0;
while not eof do
begin
inc(qn);
read(questions[qn].x, questions[qn].y);
end;
dfs(root);
for i := 1 to qn do
writeln(questions[i].ans);
close(input); close(output);
end.