STL和并查集應(yīng)用的學(xué)習(xí)心得是什么

這篇文章給大家介紹STL和并查集應(yīng)用的學(xué)習(xí)心得是什么，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

創(chuàng)新互聯(lián)專業(yè)IDC數(shù)據(jù)服務(wù)器托管提供商，專業(yè)提供成都服務(wù)器托管，服務(wù)器租用，德陽機(jī)房服務(wù)器托管，德陽機(jī)房服務(wù)器托管，成都多線服務(wù)器托管等服務(wù)器托管服務(wù)。

先介紹一下今天分享的題目

題目簡(jiǎn)述：有 n 個(gè)人，其中存在很多對(duì)朋友關(guān)系（不排除有的人沒有朋友），這種朋友關(guān)系滿足對(duì)稱、傳遞性質(zhì)（是否是自反關(guān)系對(duì)這道題沒有影響），即 如果A 和 B 是朋友，就有 B 和 A 是朋友； 如果 A 和 B 是朋友且 B 和 C 是朋友，就有 A 和 C 也是朋友關(guān)系。簡(jiǎn)言之：滿足朋友關(guān)系的人要么有直接的朋友關(guān)系，要么兩人有共同的朋友。

由上述特性可以在一個(gè)群體間建立起很多個(gè)關(guān)系網(wǎng)絡(luò)。

分析一下建立的朋友關(guān)系網(wǎng)絡(luò)具備的特征。對(duì)稱性說明該關(guān)系是無向關(guān)系，此外該網(wǎng)絡(luò)還滿足傳遞性，舉個(gè)例子：如果其中一個(gè)關(guān)系網(wǎng)絡(luò)中有 1 、2、 3、 4  這四個(gè)人，

已知

1  < - > 2

2  < - > 3 

1  < - > 4

則

由  1  < - > 2 與 2  < - > 3  可以得出 1 < - > 3

由  1  < - > 2 與 1  < - > 4  可以得出 2 < - > 4

由  2  < - > 3 與 2  < - > 4  可以得出 3 < - > 4

總結(jié)：

編號(hào) 1 的朋友為：2 、3 、4

編號(hào) 2 的朋友為：1 、3 、4

編號(hào) 3 的朋友為：1 、2 、4

編號(hào) 4 的朋友為：1 、2 、3

由此可以得出結(jié)論，這個(gè)網(wǎng)絡(luò)中任意兩個(gè)人都必須滿足朋友關(guān)系，且一個(gè)人一旦能與該網(wǎng)絡(luò)某一個(gè)人發(fā)生關(guān)系，此人同樣與其他所有人都有關(guān)系。如果一個(gè)人有朋友，那么這些互為朋友的人必然能夠形成一個(gè)封閉的關(guān)系網(wǎng)絡(luò)，這就形成了兩個(gè)極端：要么孤身一人沒有朋友，要么就必須和所在關(guān)系網(wǎng)絡(luò)中所有人成為朋友。用圖論的知識(shí)解釋：根據(jù)朋友關(guān)系的對(duì)稱性可以得出這個(gè)題目中形成的圖是無向圖，形成的關(guān)系網(wǎng)絡(luò)要么是平凡圖（只有一個(gè)孤立點(diǎn)），要么是完全圖（任意兩點(diǎn)之間均連通）。

---

題目要求：第一行給出總?cè)藬?shù) n 和 總關(guān)系對(duì)數(shù) m，將 n 個(gè)人從 1 到 n 進(jìn)行編號(hào)，并給出滿足朋友關(guān)系的 m 對(duì)編號(hào)，試判斷給出的 m 對(duì)關(guān)系是否構(gòu)成了滿足題目所述朋友關(guān)系的網(wǎng)絡(luò)體系。是輸出 YES ，否則輸出 NO 。

輸入輸出數(shù)據(jù)要求如下：

m 和 n 均不超過 150 000 。

測(cè)試樣例如下：

---

在對(duì)題目梗概了解之后，不妨先來觀察一下測(cè)試樣例。

以第一組測(cè)試樣例為例進(jìn)行分析：

n ＝ 4 ，m ＝ 3 ，由 3 對(duì)朋友關(guān)系可以建成如下關(guān)系網(wǎng)絡(luò)體系：

由上圖可以看出 左半部分滿足完全圖，右半部分滿足平凡圖，該體系滿足題目所要求的朋友關(guān)系，因此輸出答案 YES 。

再來看第二組測(cè)試數(shù)據(jù)：

n ＝ 4 ，m ＝ 4 ，由所給四對(duì)關(guān)系可以建成如下關(guān)系網(wǎng)絡(luò)體系：

由上圖可以看出，4 與 2 、1均未直接連接，因此不滿足完全圖條件，答案為 NO 。

---

在對(duì)上面兩個(gè)樣例進(jìn)行分析后發(fā)現(xiàn)，判斷一個(gè)關(guān)系網(wǎng)絡(luò)體系是否滿足條件，只需要對(duì)每一個(gè)連通分量進(jìn)行判斷，如果其中存在一個(gè)既不是完全圖也不是平凡圖的分量，那么這個(gè)體系就不滿足條件。

人眼去觀察的時(shí)候，可能一眼就能看出一個(gè)連通分量甚至一個(gè)關(guān)系網(wǎng)絡(luò)體系是不是滿足條件，但是計(jì)算機(jī)怎么判斷呢？計(jì)算機(jī)判斷的時(shí)候，必須有一個(gè)固定模式形成的標(biāo)準(zhǔn)，用這個(gè)標(biāo)準(zhǔn)和形成的實(shí)例進(jìn)行對(duì)比，完全匹配的是正確的，不完全匹配則是錯(cuò)誤的。這個(gè)過程分為以下兩步：

第一步：應(yīng)該建立起輸入信息所給的關(guān)系網(wǎng)絡(luò)體系，并將其儲(chǔ)存。建立關(guān)系網(wǎng)絡(luò)體系分為兩個(gè)方面，第一個(gè)方面，由于題目要求判斷給定的關(guān)系是否滿足條件，因此要將原來給定的 m 對(duì)關(guān)系存儲(chǔ)，第二個(gè)方面，由于朋友關(guān)系本身具備的特征，要將對(duì)稱性和傳遞性的關(guān)系體現(xiàn)出來，也就意味著，在輸入的過程中，需要對(duì)圖進(jìn)行完善，將對(duì)稱性和傳遞性所產(chǎn)生的關(guān)系填充。因此，該題目必須建立兩個(gè)獨(dú)立的結(jié)構(gòu)，一個(gè)單純存儲(chǔ)題目給定的關(guān)系，另一個(gè)則用來存儲(chǔ)經(jīng)過修正的關(guān)系網(wǎng)絡(luò)體系。

第二步：將原關(guān)系和修正關(guān)系進(jìn)行對(duì)比。

---

理論知識(shí)介紹完畢，下面是具體的實(shí)現(xiàn)方案：

和以往一樣，介紹普通思路和修改思路兩種方案

方案一

1. 原關(guān)系的存儲(chǔ)

   原來的關(guān)系給的是 m 對(duì)朋友的編號(hào)（不重復(fù)），由于要滿足對(duì)稱性關(guān)系，因此應(yīng)該存儲(chǔ)雙向關(guān)系，回憶一下，最直觀的存儲(chǔ)圖的結(jié)構(gòu)是－－鄰接矩陣，說得直白一點(diǎn)就是二維數(shù)組，這種結(jié)構(gòu)存儲(chǔ)圖的好處是，查找任意兩個(gè)元素之間的關(guān)系，時(shí)間復(fù)雜度是 o（1），但這種結(jié)構(gòu)缺點(diǎn)比較致命，空間利用率不高且對(duì)整個(gè)圖進(jìn)行遍歷時(shí)，時(shí)間消耗太多。本題m、 n 的范圍給的是150 000，開二維數(shù)組來實(shí)現(xiàn)肯定不現(xiàn)實(shí)（我不會(huì)告訴你我嘗試的時(shí)候程序崩潰到連數(shù)字都無法讀入）；另外還有一種方法用來存儲(chǔ)圖結(jié)構(gòu)－－鄰接表，這種結(jié)構(gòu)空間利用率是比較高的，但是，鏈表的實(shí)現(xiàn)編寫起來比較麻煩，稍有不慎，就會(huì)有指針越界的錯(cuò)誤出現(xiàn)。不過在對(duì)鏈表操作熟悉的前提下，也不失為一種可行方案。

2. 修正關(guān)系的存儲(chǔ)

   修正關(guān)系要滿足對(duì)稱性和傳遞性，根據(jù)題目所給的要求，相互之間存在朋友關(guān)系的人，放在同一個(gè)集合中即可。為什么僅僅存入同一個(gè)集合就可以呢？因?yàn)楸绢}中任一關(guān)系網(wǎng)絡(luò)均為無向完全圖，也就是每個(gè)關(guān)系網(wǎng)絡(luò)中的任何一個(gè)個(gè)體都與同一關(guān)系網(wǎng)絡(luò)內(nèi)其余所有個(gè)體相聯(lián)系，所有成員不存在特殊需要標(biāo)記的特性。如果僅僅需要將所有成員分成若干個(gè)集合，那么用并查集來實(shí)現(xiàn)這一步驟是再合適不過了。

   并查集實(shí)現(xiàn)的功能：按照某種特定的關(guān)系，將所有元素劃分為若干集合，并在每個(gè)集合中選出一個(gè)代表元素（俗稱father）來代表該集合，這種行為類似于在學(xué)校這樣的大環(huán)境中分了若干個(gè)班級(jí)，每個(gè)班級(jí)選出一個(gè)班長(zhǎng)，由班長(zhǎng)作為班級(jí)的代表和外界進(jìn)行溝通交流。

3. 原關(guān)系和修正關(guān)系的對(duì)比

       由于修正關(guān)系是按照正確的關(guān)系建立的關(guān)系網(wǎng)絡(luò)，因此需要判斷的是原關(guān)系是否有不同于修正關(guān)系的地方，即對(duì)于修正關(guān)系中出現(xiàn)的每一對(duì)關(guān)系，原關(guān)系圖中是否存儲(chǔ)了該關(guān)系。按照這種思路每在修正關(guān)系網(wǎng)絡(luò)中找到一對(duì)關(guān)系，就需要在存儲(chǔ)原關(guān)系的鄰接矩陣（或鄰接表）中查找該關(guān)系是否存在。這種思路的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)超過 o（n＊n），在150 000 這樣規(guī)模的數(shù)據(jù)上是不可取的。

原關(guān)系和修正關(guān)系的存儲(chǔ)結(jié)構(gòu)比較好改進(jìn)，但是關(guān)系對(duì)比這個(gè)方向怎么改進(jìn)？既然遍歷會(huì)超時(shí)，能不能換個(gè)思路進(jìn)行改進(jìn)呢？現(xiàn)在重新捋一下思路，完全圖有很多性質(zhì)，我們能不能利用它的某些性質(zhì)避開對(duì)整個(gè)圖的遍歷呢？對(duì)于一個(gè) n 個(gè)節(jié)點(diǎn)的完全圖，其中的每一個(gè)節(jié)點(diǎn)必然與其余節(jié)點(diǎn)相連接，也就意味著與之相關(guān)聯(lián)的關(guān)系個(gè)數(shù)為 n－1，那么只需要確定每個(gè)關(guān)系網(wǎng)絡(luò)中所含的節(jié)點(diǎn)的個(gè)數(shù) n ，再對(duì)原圖進(jìn)行遍歷，判斷每個(gè)節(jié)點(diǎn)是否與所在關(guān)系網(wǎng)絡(luò)滿足上述關(guān)系即可。

現(xiàn)在問題轉(zhuǎn)化成了兩個(gè)簡(jiǎn)單的問題：

一、求修正關(guān)系網(wǎng)絡(luò)體系中連通分支的個(gè)數(shù)以及對(duì)應(yīng)的節(jié)點(diǎn)數(shù)。

二、求解原關(guān)系網(wǎng)絡(luò)體系中與每個(gè)節(jié)點(diǎn)相關(guān)的關(guān)系個(gè)數(shù)并與修正關(guān)系中對(duì)應(yīng)的個(gè)數(shù)進(jìn)行對(duì)比。

準(zhǔn)備好所有需要用的數(shù)據(jù)，只需要一次遍歷，時(shí)間復(fù)雜度為 o（n）就可完成。這就產(chǎn)生了如下方案。

方案二

1. 原關(guān)系的存儲(chǔ)

   利用 STL 中的 vector 容器，實(shí)現(xiàn)對(duì)原關(guān)系網(wǎng)絡(luò)體系的動(dòng)態(tài)存儲(chǔ)，開 1e6 的 vector 數(shù)組 g［1e6］，將與編號(hào) i 相關(guān)的所有個(gè)體存入 g［i］分量中。這個(gè)時(shí)候，直接調(diào)用 g ［i］. size（）函數(shù)，就可求出與 i 有關(guān)的關(guān)系個(gè)數(shù)。（需要注意的一點(diǎn)就是，在此建立的關(guān)系是雙向的）

2. 修正關(guān)系的存儲(chǔ)

   對(duì)于修正關(guān)系網(wǎng)絡(luò)體系，可以使用并查集思想對(duì) father 數(shù)組進(jìn)行修正，由于在原關(guān)系和修正關(guān)系的對(duì)比過程中，用到的只有連通分支的代表和節(jié)點(diǎn)總數(shù)的對(duì)應(yīng)關(guān)系，因此，可以利用STL 中的 map 容器，將兩者的映射關(guān)系存入即可。

3. 原圖和修正圖的對(duì)比

   逐個(gè)比較編號(hào) i 的 分量的關(guān)系數(shù) g ［i］. size（）和 map 中 存儲(chǔ)的 i 所在關(guān)系網(wǎng)絡(luò)    的節(jié)點(diǎn)數(shù) map［ find（ i ）］是否滿足  

   map［ find（ i ）］－1 ＝ g［i］ . size（）

這就實(shí)現(xiàn)了 建圖而避開對(duì)圖遍歷 的目的。

關(guān)于STL和并查集應(yīng)用的學(xué)習(xí)心得是什么就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

分享名稱：STL和并查集應(yīng)用的學(xué)習(xí)心得是什么
當(dāng)前路徑：http://muchs.cn/article42/jcpshc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、微信公眾號(hào)、手機(jī)網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站、企業(yè)網(wǎng)站制作、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)