題目描述 若某個家族人員過於龐大,要判斷兩個是否是親戚,確實還很不容易,現在給出某個親戚關係圖,求任意給出的兩個人是否具有親戚關係。 規定:x和y是親戚,y和z是親戚,那麼x和z也是親戚。如果x,y是親戚,那麼x的親戚都是y的親戚,y的親戚也都是x的親戚。 輸入輸出格式 輸入描述: 第一行:三個整數 ...
題目描述
若某個家族人員過於龐大,要判斷兩個是否是親戚,確實還很不容易,現在給出某個親戚關係圖,求任意給出的兩個人是否具有親戚關係。
規定: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個詢問的答案為“具有”或“不具有”親戚關係。
輸入輸出樣例
輸入樣例:
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
輸出樣例:
Yes
Yes
No
思路
並查集。先將已知的親戚關係合併,再尋找要查詢的親戚的根結點。若根結點相同,輸出Yes,反之,輸出No。
代碼
#include<stdio.h> int fa[100000],b[100000]; int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } void unionn(int x,int y) { x=find(x);y=find(y); fa[y]=x; } int main() { int i,n,m,q,x,y; scanf("%d%d%d",&n,&m,&q); for(i=1;i<=n;i++) fa[i]=i; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); unionn(x,y); } for(i=1;i<=q;i++) { scanf("%d%d",&x,&y); if(find(x)==find(y)) b[i]=1; } for(i=1;i<=q;i++) { if(b[i]==1) printf("Yes\n"); else printf("No\n"); } return 0; }View Code