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.

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。