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

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

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

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

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

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

已知

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é)：

編號 1 的朋友為：2 、3 、4

編號 2 的朋友為：1 、3 、4

編號 3 的朋友為：1 、2 、4

編號 4 的朋友為：1 、2 、3

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

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

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

m 和 n 均不超過 150 000 。

測試樣例如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

方案一

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

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

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

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

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

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

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

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

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

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

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

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

方案二

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

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

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

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

3. 原圖和修正圖的對比

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

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

   
   

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

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