• 集合，數(shù)學(xué)中默認指無序集，用于表達元素的聚合關(guān)系。兩個元素只有屬于同一個集合與不屬于同一集合兩種關(guān)系。

  創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比余姚網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式余姚網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋余姚地區(qū)。費用合理售后完善，十多年實體公司更值得信賴。

常見實現(xiàn)方式

unordered_set,unordered_map,并查集,哈希表,啟發(fā)式可并堆

• 在實際應(yīng)用中，可能需要關(guān)心集合元素順序。集合上定義偏序關(guān)系（即≤號），可構(gòu)成一個偏序集。有序性作為重要規(guī)律，可引入算法（如二分法）提升運行效率。

偏序集實現(xiàn)方式

set，map，二叉排序樹（平衡二叉樹）

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（disjoint sets）的合并及查詢問題。

P1551 親戚

題目描述：

若某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現(xiàn)在給出某個親戚關(guān)系圖，求任意給出的兩個人是否具有親戚關(guān)系。

規(guī)定：xx 和 yy 是親戚，yy 和 zz 是親戚，那么 xx 和 zz 也是親戚。如果 xx，yy 是親戚，那么 xx 的親戚都是 yy 的親戚，yy 的親戚也都是 xx 的親戚。

思路:

1.初始化每個人的祖先就是自己

2.輸入兩個人,然后將兩個人的祖先合并

3.輸入,判斷兩個人的祖先是否相同(查找兩個人的祖先是否相同),輸出判斷的結(jié)果

這個題目是一個模板題，我們使用數(shù)組 fa 來存儲“代表”。代表具有傳遞性。當(dāng)查找代表時，需要遞歸地向上，直到代表為自身。

int find(int x) { // 查詢集合的“代表”
    if (x == fa[x])return x;
    return find(fa[x]);
}

當(dāng)合并兩個元素時，需先判斷兩者是否屬于同一集合。若否，則將其中一個集合的代表設(shè)置為另一方的代表。

void join(int c1, int c2) { // 合并兩集合
    // f1為c1的代表，f2為c2的代表
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2) fa[f1] = f2;
}

main函內(nèi)容

// 初始化
for (int i = 1; i<= n; ++i)
    fa[i] = i;
    // 合并親屬關(guān)系
    for (int i = 0; i< m; ++i) {
    cin >>x >>y;
    join(x, y);
}
// 根據(jù)代表是否相同，查詢親屬關(guān)系
for (int i = 0; i< p; ++i) {
    cin >>x >>y;
if (find(x) == find(y))
    cout<< "Yes"<< endl;
else
    cout<< "No"<< endl;
}

即成功AC題目

1. • 按秩合并

在執(zhí)行合并操作時，將更小的樹連接到更大的樹上，這樣的優(yōu)化方式就稱為“按秩合并”

2. • 路徑壓縮

在執(zhí)行查找的過程中，扁平化樹的結(jié)構(gòu)，這樣的優(yōu)化方式稱為“路徑壓縮“

// 一定不要忘了初始化，每個元素單獨屬于一個集合

void init() {
    for (int i = 1; i<= n; i++)
        f[i] = i;
}
int find(int x) { // 查詢集合的“代表”
    if (x == fa[x])return x;
    return fa[x] = find(fa[x]); // 路徑壓縮
}
void join(int c1, int c2) { // 合并兩個集合
    // f1為c1的代表，f2為c2的代表
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2) {
        if (size[f1]< size[f2]) // 取較大者作為代表
            swap(f1, f2);
        fa[f2] = f1;
        size[f1] += size[f2]; // 只有“代表”的size是有效的
    }
}

以上為路徑壓縮優(yōu)化后的并查集模板。

在并查集中同時使用上面的這兩種優(yōu)化方法，會將查找與合并的平均時間復(fù)雜度降低到常數(shù)水平（漸進最優(yōu)算法）。

“散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

1.字符串哈希：任意兩個字符串兩兩比較時間上必然是不可取的，時間復(fù)雜度。時間只允許處理每一個字符串僅一次。

2. 哈希函數(shù)：理論表明，并不是任意選擇 Hash 函數(shù)都能取得同樣的效果。

使用較大的質(zhì)數(shù)作為模數(shù)

模數(shù)越大，空間越多，越難以沖突。

同時，由于質(zhì)數(shù)除了1和自身外沒有其他因子，包含乘除運算

的 Hash 函數(shù)不會因為有公因子而導(dǎo)致不必要的 Hash 沖突。

使用復(fù)雜的 Hash 函數(shù)

直接取模是最簡單的方式。

但復(fù)雜的 Hash 函數(shù)可使值域分布更均勻，降低沖突的可能。

模運算可以將數(shù)值折疊到一個小區(qū)間內(nèi)。但是還有一個問題，折疊之后，不同的數(shù)可能映射到同一個區(qū)域，這一現(xiàn)象稱為 Hash 沖突。

Hash有三種解決方法：

1. 使用穩(wěn)健的 Hash 函數(shù)，效率最高，沖突率最高

2. 使用十字鏈表，完全解決沖突，效率較低

3. 使用 Multi-Hash，折中的方法

使用鏈表（或 std::vector 等結(jié)構(gòu)）將 Hash 沖突的元素保存起來。

這樣，查找一個元素時只需要與 Hash 沖突的較少元素進行比較。

vectorhash[maxh];

// 以下是插入集合的方式，查找也是類似

void int insert(x){
    int h = f(x); //計算哈希值
    for (int i == 0, sz=hash[h].size(); i

用這種方式可以完全解決 Hash 沖突問題。但是查找元素的復(fù)雜度會有所上升（取決于 Hash 沖突的次數(shù)）。

string s; // ......
int hash = 0;
for (int i = 0; s[i]; i++)
    // 計算base進制下模mod的值作為hash值
    hash = ((long long)hash * base + s[i]) % mod;

unordered_sets; //創(chuàng)建Type類型的集合
s.insert(x); // 插入元素x
s.erase(x); // 刪除值為x的元素
s.erase(it); // 刪除it所指的元素
s.end(); // 返回末位哨兵的迭代器
s.find(x); // 查詢x；不存在則返回s.end()
s.empty(); // 判斷是否為空
s.size(); // 返回集合的大小

sets; // 創(chuàng)建一個Type類型的集合
s.insert(x); // 插入元素x
s.erase(x); // 刪除值為x的元素
s.erase(it); // 刪除it所指的元素
s.end(); // 返回末位哨兵的迭代器
s.find(x); // 查詢x；不存在則返回s.end()
s.empty(); // 判斷是否為空
s.size(); // 返回集合的大小
s.upper_bound(x); // 查詢大于x的最小元素
s.lower_bound(y); // 查詢不小于x的最小元素

unordered_mapm; // 創(chuàng)建T1到T2的映射
// 其中T1稱為鍵key，T2稱為值value
m.insert({a,b});// 創(chuàng)建映射a->b
m.erase(a); // 刪除key為a的映射
m.erase(it); // 刪除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 尋找鍵x；若不存在則返回m.end()
m.empty(); // 判斷是否為空
m.size(); // 返回映射數(shù)目
m[a] = b; // 修改a映射為b；若不存在則創(chuàng)建

mapm; // 創(chuàng)建一個T1到T2的映射
// 其中T1稱為鍵key，T2稱為值value
m.insert({a,b});// 創(chuàng)建映射a->b
m.erase(a); // 刪除key為a的映射
m.erase(it); // 刪除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 尋找鍵x；若不存在則返回m.end()
m.empty(); // 判斷是否為空
m.size(); // 返回映射數(shù)目
m[a] = b; // 修改a映射為b；若不存在則創(chuàng)建
m.upper_bound(x); // 查詢大于x的最小鍵
m.lower_bound(x); // 查詢不小于x的最小鍵

//我們可以使用數(shù)組來做這個題目，但是很明顯數(shù)據(jù)計算時間復(fù)雜度后會超時，由題目可以看每一個key都有一個value，我們就可以使用map來做這個題目，大大降低
#include