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] ofrecord x, y: longint; ans: longint; end; qn, n, i, m, x, y, root: longint;
functionfind(x: longint): longint; begin if x = sets[x] thenexit(x); sets[x] := find(sets[x]); exit(sets[x]); end;
proceduredfs(x: longint); var i: longint; begin visited[x] := true; //对于两个节点都已访问到的询问,其结果已经出来了 for i := 1to 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) elseif questions[i].y = x then questions[i].ans := find(questions[i].x); end; for i := 1to n do begin ifnot a[i, x] or visited[i] thencontinue; 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 := 1to n do sets[i] := i; for i := 1to m do begin read(x, y); a[x, y] := true; a[y, x] := True; end; read(root); qn := 0; whilenot eof do begin inc(qn); read(questions[qn].x, questions[qn].y); end; dfs(root); for i := 1to qn do writeln(questions[i].ans);
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.