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)文章
這篇文章主要主要為大家詳細(xì)介紹了如何利用C++和OpenGL實(shí)現(xiàn)三角形的繪制，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起動(dòng)手嘗試一下2022-06-06
這篇文章主要給大家介紹了關(guān)于C/C++經(jīng)典算法之約瑟夫問題的相關(guān)資料,約瑟夫環(huán)問題是一道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)的題目,本文介紹了解決約瑟夫問題的三種方法,需要的朋友可以參考下2021-07-07
C語言數(shù)據(jù)結(jié)構(gòu)之判斷循環(huán)鏈表空與滿
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之判斷循環(huán)鏈表空與滿的相關(guān)資料,希望通過本文能幫助到大家，讓大家掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
C語言利用結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言利用結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
std::future通常由某個(gè)Provider創(chuàng)建,與std::async一起使用,本文主要介紹了C++筆記之std::future的用法小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下2023-10-10
抽象類(abstract class)和接口(interface)的概念是面向?qū)ο笤O(shè)計(jì)中常用的概念, 也是比較容易混淆的概念. 在這里, 我提出一種區(qū)分它們的思路2013-04-04
這篇文章主要介紹了C++非遞歸遍歷磁盤文件和遞歸遍歷磁盤文件的程序示例,大家可以參考使用二種方法2013-11-11
探究C++中指針與數(shù)組運(yùn)算符優(yōu)先級(jí)
C++中與指針和數(shù)組相關(guān)的運(yùn)算符優(yōu)先級(jí),通過實(shí)際代碼示例解釋了運(yùn)算符的左結(jié)合與右結(jié)合方式,以及如何使用圓括號(hào)()來改變默認(rèn)的結(jié)合順序,文章還提供了一個(gè)優(yōu)先級(jí)表,列出了運(yùn)算符的優(yōu)先級(jí)和結(jié)合性,幫助讀者更好地理解復(fù)雜表達(dá)式中運(yùn)算符的調(diào)用順序2024-10-10
本篇文章主要介紹了從單鏈表的創(chuàng)建、遍歷到節(jié)點(diǎn)的插入、刪除與查找功能的實(shí)現(xiàn),有需要的朋友可以參考下2015-07-07
vsCode配置import@路徑提示的實(shí)現(xiàn)步驟
在導(dǎo)入文件設(shè)置路徑的時(shí)候方便了很多,本文主要介紹了vsCode配置import@路徑提示的實(shí)現(xiàn)步驟,具有一定的參考價(jià)值,感興趣的可以了解一下2023-08-08