STL和并查集應用的學習心得是什么

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

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

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

由上述特性可以在一個群體間建立起很多個關系網絡。

分析一下建立的朋友關系網絡具備的特征。對稱性說明該關系是無向關系，此外該網絡還滿足傳遞性，舉個例子：如果其中一個關系網絡中有 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

總結：

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

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

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

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

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

題目要求：第一行給出總人數 n 和 總關系對數 m，將 n 個人從 1 到 n 進行編號，并給出滿足朋友關系的 m 對編號，試判斷給出的 m 對關系是否構成了滿足題目所述朋友關系的網絡體系。是輸出 YES ，否則輸出 NO 。

輸入輸出數據要求如下：

m 和 n 均不超過 150 000 。

測試樣例如下：

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

以第一組測試樣例為例進行分析：

n ＝ 4 ，m ＝ 3 ，由 3 對朋友關系可以建成如下關系網絡體系：

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

再來看第二組測試數據：

n ＝ 4 ，m ＝ 4 ，由所給四對關系可以建成如下關系網絡體系：

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

在對上面兩個樣例進行分析后發現，判斷一個關系網絡體系是否滿足條件，只需要對每一個連通分量進行判斷，如果其中存在一個既不是完全圖也不是平凡圖的分量，那么這個體系就不滿足條件。

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

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

第二步：將原關系和修正關系進行對比。

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

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

方案一

1. 原關系的存儲

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

2. 修正關系的存儲

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

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

3. 原關系和修正關系的對比

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

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

現在問題轉化成了兩個簡單的問題：

一、求修正關系網絡體系中連通分支的個數以及對應的節點數。

二、求解原關系網絡體系中與每個節點相關的關系個數并與修正關系中對應的個數進行對比。

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

方案二

1. 原關系的存儲

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

2. 修正關系的存儲

   對于修正關系網絡體系，可以使用并查集思想對 father 數組進行修正，由于在原關系和修正關系的對比過程中，用到的只有連通分支的代表和節點總數的對應關系，因此，可以利用STL 中的 map 容器，將兩者的映射關系存入即可。

3. 原圖和修正圖的對比

   逐個比較編號 i 的 分量的關系數 g ［i］. size（）和 map 中 存儲的 i 所在關系網絡    的節點數 map［ find（ i ）］是否滿足  

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

   
   

這就實現了 建圖而避開對圖遍歷 的目的。

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