并查集：把集合中元素的關(guān)系構(gòu)造為一棵樹(shù)；

路徑壓縮優(yōu)化：在查詢子節(jié)點(diǎn)的根的時(shí)候，壓縮整個(gè)枝干到root，形成菊花樹(shù)；

子樹(shù)合并優(yōu)化：在合并兩棵樹(shù)的時(shí)候，把深度小的樹(shù)作為子樹(shù)合到深度大的樹(shù)上，合并后的樹(shù)根深度++（注意排除樹(shù)根相同的假合并）

兩種優(yōu)化一起使用：路徑壓縮時(shí)要保證root的深度更新

相比DFS或BFS，DUS的優(yōu)點(diǎn)是在多次查詢時(shí)，每次查詢都可以優(yōu)化以后查詢的速度。對(duì)于每個(gè)分裂的連通圖（樹(shù)枝），僅第一次查詢要遍歷整條枝干，往后都是O(1)復(fù)雜度。

（洛谷P1551）親戚

題目背景
若某個(gè)家族人員過(guò)于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容易，現(xiàn)在給出某個(gè)親戚關(guān)系圖，求任意給出的兩個(gè)人是否具有親戚關(guān)系。
題目描述
規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。
輸入格式
第一行：三個(gè)整數(shù)n,m,p，（n<=5000,m<=5000,p<=5000），分別表示有n個(gè)人，m個(gè)親戚關(guān)系，詢問(wèn)p對(duì)親戚關(guān)系。
以下m行：每行兩個(gè)數(shù)Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有親戚關(guān)系。
接下來(lái)p行：每行兩個(gè)數(shù)Pi，Pj，詢問(wèn)Pi和Pj是否具有親戚關(guān)系。
輸出格式
P行，每行一個(gè)’Yes’或’No’。表示第i個(gè)詢問(wèn)的答案為“具有”或“不具有”親戚關(guān)系。

本題中，如果用搜索算法，每次查詢效率為O(n)，而用并查集可以做到平均效率接近O(1)。