並查集（Union-Find）是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合併及查詢問題。 並查集存在兩個操作（1.Union 聯合 2.finddeputy 查找代表結點） 和一個需要解答的問題（ issameset 是否 在一個集合中，或者說是否有同一個代表結點）。
利用map實現主要通過兩個map的對象 ，一個map<data,data>類型的fathermap，關鍵字為子結點，值為其父結點（父結點不一定就是代表結點），當我們需要查找兩個兩個元素是否在一個集合中時，只需一直向上找（函數finddupty），在找的過程中，會壓縮路徑，把沿途經過的結點直接掛在其代表結點下，看是否有共同的代表結點；
一個map<data,int>類型的sizemap，key為結點，value為其子結點的個數（這個個數只對代表結點有效，子結點無效），主要用處是在合併（union）時將子結點較少的代表結點掛在子結點代表較多的代表結點下，且sizemap中父結點對應的value要加上子結點較少的代表的結點個數。
代碼如下：
#include<map> #include<list> #include<iostream> using namespace std; template<typename data> class Unionfindset{ public: void makesets(list<data> nodes) { fathermap.clear(); sizemap.clear(); for(auto node:nodes) { fathermap[node]=node; sizemap[node]=1; } } //尋找代表結點，且路徑壓縮 data findduputy(data node) { data father=fathermap[node]; if(father!=node) { return findduputy(father); } fathermap[node]=father; return father; } void Union(data a ,data b) { data ahead=findduputy(a); data bhead=findduputy(b); if(ahead!=bhead) { data asize=sizemap[a]; data bsize=sizemap[b]; if(asize<bsize) { fathermap[a]=b; sizemap[b]=bsize+asize; } else { fathermap[b]=a; sizemap[a]=bsize+asize; } } } bool issameset(data a,data b) { return findduputy(a)==findduputy(b); } private: map<data,data> fathermap; map<data,data> sizemap; };
[qp18502452 ] C++利用map實現並查集已經有256次圍觀