C++并查集親戚(Relations)算法實例
更新時間：2015年04月20日 14:43:30 作者：司青
這篇文章主要介紹了C++并查集親戚(Relations)算法,實例分析了并查集親戚算法的原理與實現技巧,具有一定參考借鑒價值,需要的朋友可以參考下
本文實例講述了C++并查集親戚(Relations)算法。分享給大家供大家參考。具體分析如下：
題目： 親戚(Relations)
或許你并不知道，你的某個朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孫子。如果能得到完整的家譜，判斷兩個人是否親戚應該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關系實非人力所能及.在這種情況下，最好的幫手就是計算機。
為了將問題簡化，你將得到一些親戚關系的信息，如同Marry和Tom是親戚，Tom和B en是親戚，等等。從這些信息中，你可以推出Marry和Ben是親戚。請寫一個程序，對于我們的關心的親戚關系的提問，以最快的速度給出答案。
參考輸入輸出格式 輸入由兩部分組成。
第一部分以N，M開始。N為問題涉及的人的個數(1 ≤ N ≤ 20000)。這些人的編號為1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有兩個數ai, bi，表示已知ai和bi是親戚.
第二部分以Q開始。以下Q行有Q個詢問(1 ≤ Q ≤ 1 000 000)，每行為ci, di，表示詢問ci和di是否為親戚。
對于每個詢問ci, di，若ci和di為親戚，則輸出Yes，否則輸出No。
樣例輸入與輸出
輸入
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
輸出
Yes
No
Yes
如果這道題目不用并查集，而只用鏈表或數組來存儲集合，那么效率很低，肯定超時。
代碼如下：
#include <iostream>
#include <cstdio>
using namespace std;
int father[20010]; //father[i]表示i的父親
int Find(int a) //查找其父親并壓縮路徑
{
if(father[a] != a)
father[a] = Find(father[a]);
return father[a];
}
int main()
{
int N,M;
int a,b;
scanf("%d%d",&N,&M);
//給每個元素建立一個集合
for(int i = 1 ; i <= N ; ++i)
father[i] = i;
//合并
for(int i = 0 ; i < M ; ++i)
{
scanf("%d%d",&a,&b);
a = Find(a);
b = Find(b);
father[a] = b;
}
//查詢
scanf("%d",&M);
while(M--)
{
scanf("%d%d",&a,&b);
a = Find(a);
b = Find(b);
if(a == b)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
希望本文所述對大家的C++程序設計有所幫助。
相關文章
本篇文章是對c語言中用字符串數組顯示菜單的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
下面小編就為大家?guī)硪黄肅++類實現單向鏈表的增刪查和反轉操作方法。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-04-04
VScode搭建C/C++開發(fā)環(huán)境的詳細過程
最近迷上了vscode,小巧美觀,最主要的是全平臺,但是vscode并不是ide,必須得自己配置環(huán)境,下面這篇文章主要給大家介紹了關于VScode搭建C/C++開發(fā)環(huán)境的詳細過程,需要的朋友可以參考下2023-06-06
這篇文章主要為大家詳細介紹了opencv幀差法找出相差大的圖像，包含訪問mat的像素值，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家詳細介紹了基于實現Qt秒表設計，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
聊聊Qt+OpenCV聯合開發(fā)之圖像的創(chuàng)建與賦值問題
這篇文章主要介紹了Qt+OpenCV聯合開發(fā)之圖像的創(chuàng)建與賦值問題，給大家介紹了圖像的克隆及拷貝問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-01-01
這篇文章主要介紹了C語言 數據結構堆排序順序存儲（升序）的相關資料,需要的朋友可以參考下2017-05-05
C++ explicit關鍵字用來修飾類的構造函數，表明該構造函數是顯式的，既然有"顯式"那么必然就有"隱式"，那么什么是顯示而什么又是隱式的呢？下面就讓我們一起來看看這方面的知識吧2013-09-09
這篇文章主要為大家介紹了Linux/C++多線程實例學習十字路口車輛調度示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
這篇文章主要介紹了c++中try catch的用法小結,需要的朋友可以參考下2018-01-01