某次參加筆試的最后一題大意如下：給定一組用戶[0..n]皆辽，以及他們之間的好友關(guān)系因苹，問這些好友構(gòu)成了多少個(gè)朋友圈缕减？
例如有用戶[1..5]庭再，好友關(guān)系有(1,2),(3,4),(4,5)捞奕，則共有兩個(gè)好友圈：[1,2]和[3,4,5]
并查集
題目的意思可以理解為給定一個(gè)無向圖，求其中連通子圖的個(gè)數(shù)拄轻。算法來自于《算法導(dǎo)論（第二版）》的第21章
對(duì)于一個(gè)并查集來說颅围，我們通常希望其支持三種操作：
MakeSet(x)：當(dāng)我們新加入一個(gè)元素，且與當(dāng)前任何節(jié)點(diǎn)有連接恨搓，因此它（目前為止）單獨(dú)成為一個(gè)集合院促。
Union(x,y)：添加兩個(gè)元素之間的聯(lián)系筏养，因此兩個(gè)元素屬于的集合需要合并成為一個(gè)集合。
FindSet(x)：查詢一個(gè)元素到底屬于哪個(gè)集合常拓。
顯然當(dāng)有n個(gè)元素時(shí)渐溶，Union操作至多有n-1次，MakeSet操作至多為n次弄抬。
代碼實(shí)現(xiàn)
可以用一個(gè)數(shù)組p來儲(chǔ)存所有元素對(duì)應(yīng)的集合茎辐。例如p[x]=1表示元素x屬于編號(hào)為1的集合。然而整個(gè)編號(hào)為1的集合可能又屬于另一個(gè)更大的集合掂恕，因此需要查詢p[1]來找到其父集合……以此類推拖陆，直到有p[a]=a為止。由此可見懊亡，這其實(shí)是一種基于樹的實(shí)現(xiàn)依啰。
-
兩種策略
- 按秩合并(union by rank)
rank可以看作是每個(gè)根節(jié)點(diǎn)的高度（并不嚴(yán)格是，其實(shí)是其高度的一個(gè)上界）店枣，合并兩棵樹樹時(shí)速警，將高度較小的樹的根指向高度較大的樹可以保證合并后的樹的高度上界不再增加。若高度相等鸯两，則合并后的樹高度加一闷旧。 - 路徑壓縮(path compression)
當(dāng)從某一結(jié)點(diǎn)以此查找到根節(jié)點(diǎn)時(shí)，可以將經(jīng)過路徑的所有節(jié)點(diǎn)的父節(jié)點(diǎn)都修改為根節(jié)點(diǎn)甩卓。但我們的方法中并不修改根節(jié)點(diǎn)的秩鸠匀，因?yàn)樾薷囊活w樹的高度需要遍歷整棵樹的所有節(jié)點(diǎn)才能確定，這顯然得不償失逾柿，這也就解釋了為什么秩并不是每棵樹的高度，而是它高度的一個(gè)上界宅此。
int MakeSet(int x)
{
p[x]=x;
rank[x]=0;
}
void Union(int a,int b)
{
int x=FindSet(a);
int y=FindSet(b);
if(rank[x]>rank[y])
{
p[y]=x;
}
else
{
p[x]=y;
}
if(rank[x]==rank[y])
{
rank[y]=rank[y]+1;
}
}
int FindSet(int x)
{
if(x!=p[x])
{
p[x]=FindSet(p[x]);
}
return p[x];
}
若MakeSet机错、Union和FindSet操作共m個(gè)，其中有n個(gè)MakeSet操作父腕，單獨(dú)使用按秩合并的策略運(yùn)行時(shí)間為
單獨(dú)使用路徑壓縮弱匪，若有n個(gè)
MakeSet操作和f個(gè)FindSet操作，運(yùn)行時(shí)間為\right)
類型推導(dǎo)
在一個(gè)函數(shù)體中璧亮，各個(gè)參數(shù)的相互作用可以看作是一個(gè)無向有環(huán)圖（DAG）萧诫。依據(jù)函數(shù)內(nèi)的各個(gè)節(jié)點(diǎn)，可以生成一系列的類型約束等式枝嘶。
圖中的代碼
proc(f)proc(x)-((f 3),(f x))等價(jià)于如下scheme代碼：
(lambda (f) (lambda (x) (- (f 3) (f x))))
或者如下C++代碼
template<typename T3,typename Tf,typename Tx>
T3 func(Tf f, Tx x)
{
return (f 3)-(f x);
}
約束生成(constraints generation)的規(guī)則如下：
得到類型等式后帘饶，接下來是對(duì)等式進(jìn)行合一(unify)和替換(substitute)操作。
合并規(guī)則如下：
關(guān)于多態(tài)的推導(dǎo)：
下面是Essentials of Programming Languages中的步驟演示
可以看到群扶，每一個(gè)等式及刻，都需要進(jìn)行
unify操作镀裤，因?yàn)轭愋拖嗟燃创硭鼈儗儆谕患稀５枰⒁獾氖墙煞梗@里的unify操作和之前提到的union并不完全相同暑劝，因?yàn)槲覀冞€需要處理函數(shù)類型。若有類似t1->t2=t3->t4的等式颗搂，則需要同時(shí)unify(t1,t3)和unify(t2,t4)担猛。另一方面，在合并類型時(shí)可能是有方向的丢氢，需要將泛化(generic)類型向具化(normalized)類型合并傅联。例如有t1=t2,t2=int，則得到t1=int,t2=int卖丸，這也意味這上文提到的按秩合并的策略在此并不可用纺且，但路徑壓縮依然可行。
更多閱讀
- 《算法導(dǎo)論》中關(guān)于并查集算法時(shí)間復(fù)雜度的證明
- Hindley-Milner類型系統(tǒng)
- 邏輯式編程與合一算法
- Recursive Type（本文中的類型推導(dǎo)僅對(duì)STLC(simply typed lambda calculus)成立稍浆，根據(jù)STLC的strong normalization特性载碌，所有STLC能表達(dá)的程序中不會(huì)有遞歸且一定終止，如果突破這一限制呢衅枫？）
