家族

ssl 1896

題目大意：

合并一些集合，然后判斷某兩個點是否在同一個集合內

原題：

題目描述

若某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關系圖，求任意給出的兩個人是否具有親戚關系。
規定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。

輸入

第一行：三個整數n,m,p，（n<=50000,m<=50000,p<=50000），分別表示有n個人，m個親戚關系，詢問p對親戚關系。以下m行：每行兩個數Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有親戚關系。接下來p行：每行兩個數Pi，Pj，詢問Pi和Pj是否具有親戚關系。

輸出

P行，每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關系。

輸入樣例

6 5 3 41 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6

輸出樣例

Yes Yes No

解題思路：

用并查集，記錄每一個點的根節點，然后直接判斷根節點是否相同就行了

代碼：

#include<cstdio> using namespace std; int n,m,t,x,y,x1,y1,dad[50005]; int find(int dep) {return dep==dad[dep]?dep:dad[dep]=find(dad[dep]);//并查集和路徑壓縮 } int main() {scanf("%d %d %d",&n,&m,&t);for (int i=1;i<=n;++i)dad[i]=i;for (int i=1;i<=m;++i){scanf("%d %d",&x,&y);x1=find(x);//查找y1=find(y);if (x1<y1) dad[y1]=x1;//合并else dad[x1]=y1;}for (int i=1;i<=t;++i){scanf("%d %d",&x,&y);if (find(x)==find(y)) printf("Yes\n");//判斷else printf("No\n");} }

總結

以上是生活随笔為你收集整理的【并查集】家族 （ssl 1896）的全部內容，希望文章能夠幫你解決所遇到的問題。

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