C++并查集親戚(Relations)算法實(shí)例
本文實(shí)例講述了C++并查集親戚(Relations)算法。分享給大家供大家參考。具體分析如下:
題目: 親戚(Relations)
或許你并不知道,你的某個(gè)朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孫子。如果能得到完整的家譜,判斷兩個(gè)人是否親戚應(yīng)該是可行的,但如果兩個(gè)人的最近公共祖先與他們相隔好幾代,使得家譜十分龐大,那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及.在這種情況下,最好的幫手就是計(jì)算機(jī)。
為了將問題簡(jiǎn)化,你將得到一些親戚關(guān)系的信息,如同Marry和Tom是親戚,Tom和B en是親戚,等等。從這些信息中,你可以推出Marry和Ben是親戚。請(qǐng)寫一個(gè)程序,對(duì)于我們的關(guān)心的親戚關(guān)系的提問,以最快的速度給出答案。
參考輸入輸出格式 輸入由兩部分組成。
第一部分以N,M開始。N為問題涉及的人的個(gè)數(shù)(1 ≤ N ≤ 20000)。這些人的編號(hào)為1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000),每行有兩個(gè)數(shù)ai, bi,表示已知ai和bi是親戚.
第二部分以Q開始。以下Q行有Q個(gè)詢問(1 ≤ Q ≤ 1 000 000),每行為ci, di,表示詢問ci和di是否為親戚。
對(duì)于每個(gè)詢問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
如果這道題目不用并查集,而只用鏈表或數(shù)組來存儲(chǔ)集合,那么效率很低,肯定超時(shí)。
代碼如下:
#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); //給每個(gè)元素建立一個(gè)集合 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; }
希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
用C++類實(shí)現(xiàn)單向鏈表的增刪查和反轉(zhuǎn)操作方法
下面小編就為大家?guī)硪黄肅++類實(shí)現(xiàn)單向鏈表的增刪查和反轉(zhuǎn)操作方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-04-04VScode搭建C/C++開發(fā)環(huán)境的詳細(xì)過程
最近迷上了vscode,小巧美觀,最主要的是全平臺(tái),但是vscode并不是ide,必須得自己配置環(huán)境,下面這篇文章主要給大家介紹了關(guān)于VScode搭建C/C++開發(fā)環(huán)境的詳細(xì)過程,需要的朋友可以參考下2023-06-06基于實(shí)現(xiàn)Qt秒表設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了基于實(shí)現(xiàn)Qt秒表設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08聊聊Qt+OpenCV聯(lián)合開發(fā)之圖像的創(chuàng)建與賦值問題
這篇文章主要介紹了Qt+OpenCV聯(lián)合開發(fā)之圖像的創(chuàng)建與賦值問題,給大家介紹了圖像的克隆及拷貝問題,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-01-01C語言 數(shù)據(jù)結(jié)構(gòu)堆排序順序存儲(chǔ)(升序)
這篇文章主要介紹了C語言 數(shù)據(jù)結(jié)構(gòu)堆排序順序存儲(chǔ)(升序)的相關(guān)資料,需要的朋友可以參考下2017-05-05C++ explicit關(guān)鍵字的應(yīng)用方法詳細(xì)講解
C++ explicit關(guān)鍵字用來修飾類的構(gòu)造函數(shù),表明該構(gòu)造函數(shù)是顯式的,既然有"顯式"那么必然就有"隱式",那么什么是顯示而什么又是隱式的呢?下面就讓我們一起來看看這方面的知識(shí)吧2013-09-09Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車輛調(diào)度
這篇文章主要為大家介紹了Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車輛調(diào)度示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-05-05