Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

保险起见,在输出前要路径压缩一次

Posted by xiaozqh at 2013-03-16 20:41:16 on Problem 1988
rt
贡献一次WA
附代码(Pascal)
var
  p,i,x,y,zero:longint;
  f,before,count:array [0..30010] of longint;
  ch:char;

function find(x:longint):longint;
begin
  if f[x]=x then exit(x);
  find:=find(f[x]);
  inc(before[x],before[f[x]]);
  f[x]:=find;
end;

procedure merge(x,y:longint);
begin
  x:=find(x); y:=find(y);
  if x=y then exit;
  f[x]:=y;
  inc(before[x],count[y]);
  inc(count[y],count[x]);
end;

begin
  readln(p);
  for i:=1 to 30000 do begin count[i]:=1; f[i]:=i; end;
  for i:=1 to p do
    begin
      read(ch);
      if ch='M' then
        begin
          readln(x,y);
          merge(x,y);
        end
      else
        begin
          readln(x);
          zero:=find(x);
          writeln(before[x]);
        end;
    end;
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator