P1551 亲戚

 1 program relation; 2 const 3   inf=‘relation.in‘; 4   outf=‘relation.out‘; 5 var 6   father:array[0..20000] of longint; 7   i,n,m,q,a,b,t1,t2:longint; 8  9 function find(apple:longint):longint;10 begin11     if father[apple]<>apple then father[apple]:=find(father[apple]);12     exit(father[apple]);13 end;14 15 procedure union(aa,bb:longint);16 begin17     father[bb]:=aa;18 end;19 20 21 begin22   //assign(input,inf);23   //assign(output,outf);24   //reset(input); rewrite(output);25 26   readln(n,m,q);27   for i:= 1 to n do28     father[i]:=i;   //init;29 30   for i:= 1 to m do31    begin32     read(a,b);33     t1:=find(a);34     t2:=find(b);35     if t1<>t2 then union(t1,t2);36    end;37 38   for i:= 1 to q do   //ask39     begin40         readln(a,b);41         if find(a)=find(b) then writeln(‘Yes‘)42           else writeln(‘No‘);43     end;44 45   close(input);46   close(output);47 end.

 1 { 2     并查集： 3     先读入，然后找两个点的flag，然后合并(后面接着前面) 4 } 5  6 program relation; 7 const 8   inf=‘relation.in‘; 9   outf=‘relation.out‘;10 var11   father:array[0..20000] of longint;12   i,n,m,q,a,b,t1,t2:longint;13 14 function find(apple:longint):longint;15 begin16     if father[apple]<>apple then father[apple]:=find(father[apple]);17     exit(father[apple]);18 end;19 20 procedure union(aa,bb:longint);21 begin22     father[bb]:=aa;23 end;24 25 begin26   //assign(input,inf);27   //assign(output,outf);28   //reset(input); rewrite(output);29 30   readln(n,m,q);31   for i:= 1 to n do32     father[i]:=i;   //init;33 34   for i:= 1 to m do35    begin36     read(a,b);37     t1:=find(a);38     t2:=find(b);39     if t1<>t2 then union(t1,t2);40    end;41 42   for i:= 1 to q do   //ask43     begin44         readln(a,b);45         if find(a)=find(b) then writeln(‘Yes‘)46           else writeln(‘No‘);47     end;48 49   close(input);50   close(output);51 end.