題目

有n個人，已知m種親戚關系，如果A和B是親戚，B和C也是親戚，那么A和C也是親戚。接下來求一些人是否為親戚。

Input

輸入由兩部分組成。
第一部分以N，M開始。N為問題涉及的人的個數,M表示已經知道M對親戚關1<=N,M<=100000，接下來M行，每行有兩個數ai, bi，表示已知ai和bi是親戚。這些人的編號為1,2,3,…, N。接下來輸入一個整數P(1<=P<=100000),表示有P次詢問，接下來P行，每行為ci, di，表示詢問ci和di是否為親戚。

Output

輸出一行：若ci和di為親戚，則輸出“Yes”，否則輸出“No”。

Sample Input

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

Sample Output

Yes
No
Yes

解題思路

并查集不解釋

代碼

#include<cstdio> using namespace std; int x,y,father[100001],n,m,p; int find(int x)//查找 {if (x!=father[x]) return father[x]=find(father[x]);else return x; } void d(int x,int y) {int fa=find(x),fb=find(y);if (fa<fb) father[fb]=fa;else father[fa]=fb; } int main() {scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) father[i]=i;for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);d(x,y);//合并}scanf("%d",&p);for (int i=1;i<=p;i++){scanf("%d%d",&x,&y);if (find(x)!=find(y)) printf("No\n");//詢問else printf("Yes\n");} }

總結

以上是生活随笔為你收集整理的jzoj1882-亲戚【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。