真是巧妙的算法!
比起树上倍增,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.
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.