真是巧妙的算法!

比起树上倍增,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.