【概述】

并查集（Union-Find Set）是一種用于分離集合操作的抽象數(shù)據(jù)類型，其處理的是集合（set）之間的關(guān)系，一般處理的是圖的連通分量，當(dāng)給出兩個(gè)的元素的一個(gè)無序?qū)?(a,b) 時(shí)，需要快速合并(union) a 和 b 所在的集合，這期間需要反復(fù)查找(find)某元素的集合。

當(dāng)遇到有關(guān)物與物之間的關(guān)系，且這種關(guān)系是可傳遞的問題時(shí)，可以優(yōu)先嘗試用并查集解決。

• 并查集的基本操作：點(diǎn)擊這里
• 并查集的刪除操作：點(diǎn)擊這里
• 帶權(quán)并查集：點(diǎn)擊這里

【例題】

1.基礎(chǔ)應(yīng)用

暢通工程（HDU-1232）：點(diǎn)擊這里

A Bug's Life（HDU-1829）：點(diǎn)擊這里

The Suspects（POJ-1611）：點(diǎn)擊這里

親戚（信息學(xué)奧賽一本通-T1346）：點(diǎn)擊這里

家庭問題（信息學(xué)奧賽一本通-T1362）：點(diǎn)擊這里

團(tuán)伙（信息學(xué)奧賽一本通-T1385）：點(diǎn)擊這里

親戚（信息學(xué)奧賽一本通-T1389）：點(diǎn)擊這里

連結(jié) / Connectivity（AtCoder-2159）：點(diǎn)擊這里

2.帶權(quán)并查集

Dragon Balls（HDU-3635）(統(tǒng)計(jì)問題)：點(diǎn)擊這里

Cube Stacking（POJ-1988）(統(tǒng)計(jì)問題)：點(diǎn)擊這里

打擊犯罪（信息學(xué)奧賽一本通-T1386）(統(tǒng)計(jì)問題)：點(diǎn)擊這里

How Many Answers Are Wrong（HDU-3038）(區(qū)間問題)：點(diǎn)擊這里

食物鏈（POJ-1182）(種類問題)：點(diǎn)擊這里
同題：食物鏈（信息學(xué)奧賽一本通-T1390）：點(diǎn)擊這里

Rochambeau（POJ-2912）(種類問題)：點(diǎn)擊這里

Zjnu Stadium（HDU-3047）(種類問題+向量計(jì)算)：點(diǎn)擊這里

搭配購(gòu)買（信息學(xué)奧賽一本通-T1387）(帶權(quán)并查集+01背包)：點(diǎn)擊這里

3.其他

Tree（HDU-5060）(統(tǒng)計(jì)連通塊中元素個(gè)數(shù))：點(diǎn)擊這里

Junk-Mail Filter（HDU 2473）(并查集刪除操作)：點(diǎn)擊這里

格子游戲（信息學(xué)奧賽一本通-T1347）(塊狀并查集)：點(diǎn)擊這里

Haybale Guessing （POJ-3657）(并查集+二分)：點(diǎn)擊這里

Segment set（HDU-1558）(并查集+線段計(jì)算)：點(diǎn)擊這里

Is It A Tree?（HDU-1325）(并查集+樹的構(gòu)建)：點(diǎn)擊這里

家譜（信息學(xué)奧賽一本通-T1388）(并查集+map)：點(diǎn)擊這里

So Easy（2019 ACM-ICPC 徐州賽區(qū)網(wǎng)絡(luò)賽 B）(并查集+unordered_map)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的树形结构 —— 并查集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。