描述 若某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關系圖，求任意給出的兩個人是否具有親戚關系。 規定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。 格式 輸入格式
第一行：三個整數n,m,p，（n<=5000,m<=5000,p<=5000），分別表示有n個人，m個親戚關系，詢問p對親戚關系。 以下m行：每行兩個數Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有親戚關系。 接下來p行：每行兩個數Pi，Pj，詢問Pi和Pj是否具有親戚關系。 輸出格式
P行，每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關系。 樣例1 樣例輸入1[復制]
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 樣例輸出1[復制]
Yes Yes No 限制 各點1S 來源 cdwind整理提交
并查集： 1.每輸入一對親戚就合并，判斷之前是否已經在同一集合可以優化時間。 2.輸入詢問的x,y時，判斷是否在同一個集合，在輸出’Yes’，不在輸出’No’。
時間復雜度：O（M）
var f:array [0..50001] of longint; i,j,n,m,p,x,y:longint;function find(a:longint):longint;begin if f[a]=a then exit(f[a]); f[a]:=find(f[a]); exit(f[a]);end;begin readln(n,m,p); for i:=1 to n do f[i]:=i; for i:=1 to m do begin readln(x,y); if find(x)<>find(y) then f[find(x)]:=f[find(y)]; end; for i:=1 to p do begin readln(x,y); if find(x)=find(y) then writeln('Yes') else writeln('No'); end;end.新聞熱點
疑難解答
