算法題目 力扣 <連通網(wǎng)絡(luò)的操作次數(shù)>
知乎博客-算法學(xué)習(xí)筆記(1) : 并查集
前言
最近在學(xué)習(xí)中遇到這樣一道題(如下所示), 在評(píng)論區(qū)一片"并查集"飄過(guò), "并查集"是什么? 這不是典型的"親戚"問(wèn)題嗎? 大學(xué)時(shí)就學(xué)過(guò), 運(yùn)用"深度優(yōu)先遍歷"方法去解就好了. 那 "并查集" 是什么?
連通網(wǎng)絡(luò)的操作次數(shù)
用以太網(wǎng)線纜將 n 臺(tái)計(jì)算機(jī)連接成一個(gè)網(wǎng)絡(luò)邢疙，計(jì)算機(jī)的編號(hào)從 0 到 n-1暖释。線纜用 connections 表示取募，其中 connections[i] = [a, b] 連接了計(jì)算機(jī) a 和 b悴能。
網(wǎng)絡(luò)中的任何一臺(tái)計(jì)算機(jī)都可以通過(guò)網(wǎng)絡(luò)直接或者間接訪問(wèn)同一個(gè)網(wǎng)絡(luò)中其他任意一臺(tái)計(jì)算機(jī)锥余。
給你這個(gè)計(jì)算機(jī)網(wǎng)絡(luò)的初始布線 connections刁品，你可以拔開任意兩臺(tái)直連計(jì)算機(jī)之間的線纜辱姨，并用它連接一對(duì)未直連的計(jì)算機(jī)誊酌。請(qǐng)你計(jì)算并返回使所有計(jì)算機(jī)都連通所需的最少操作次數(shù)蹦漠。如果不可能椭员，則返回 -1 。
示例 1：
image輸入：n = 4, connections = [[0,1],[0,2],[1,2]]
輸出：1
解釋：拔下計(jì)算機(jī) 1 和 2 之間的線纜笛园，并將它插到計(jì)算機(jī) 1 和 3 上隘击。示例 2：
image輸入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
輸出：2
簡(jiǎn)介
并查集主要用于解決一些元素分組的問(wèn)題。它管理一系列不相交的集合研铆，并支持兩種操作：
- 合并（Union）：把兩個(gè)不相交的集合合并為一個(gè)集合埋同。
- 查詢（Find）：查詢兩個(gè)元素是否在同一個(gè)集合中。
當(dāng)然棵红，這樣的定義未免太過(guò)學(xué)術(shù)化凶赁，看完后恐怕不太能理解它具體有什么用。所以我們先來(lái)看看并查集最直接的一個(gè)應(yīng)用場(chǎng)景：親戚問(wèn)題逆甜。
題目背景
若某個(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)系。
這其實(shí)是一個(gè)很有現(xiàn)實(shí)意義的問(wèn)題袍祖。我們可以建立模型底瓣，把所有人劃分到若干個(gè)不相交的集合中，每個(gè)集合里的人彼此是親戚蕉陋。為了判斷兩個(gè)人是否為親戚捐凭，只需看它們是否屬于同一個(gè)集合即可。因此寺滚，這里就可以考慮用并查集進(jìn)行維護(hù)了柑营。
并查集的引入
并查集的重要思想在于屈雄，用集合中的一個(gè)元素代表集合村视。我曾看過(guò)一個(gè)有趣的比喻，把集合比喻成幫派酒奶，而代表元素則是幫主蚁孔。接下來(lái)我們利用這個(gè)比喻，看看并查集是如何運(yùn)作的惋嚎。
最開始杠氢，所有大俠各自為戰(zhàn)。他們各自的幫主自然就是自己另伍。（對(duì)于只有一個(gè)元素的集合鼻百，代表元素自然是唯一的那個(gè)元素）
現(xiàn)在1號(hào)和3號(hào)比武绞旅，假設(shè)1號(hào)贏了（這里具體誰(shuí)贏暫時(shí)不重要），那么3號(hào)就認(rèn)1號(hào)作幫主（合并1號(hào)和3號(hào)所在的集合温艇，1號(hào)為代表元素）因悲。
現(xiàn)在2號(hào)想和3號(hào)比武（合并3號(hào)和2號(hào)所在的集合），但3號(hào)表示勺爱，別跟我打晃琳，讓我?guī)椭鱽?lái)收拾你（合并代表元素）。不妨設(shè)這次又是1號(hào)贏了琐鲁，那么2號(hào)也認(rèn)1號(hào)做幫主卫旱。
現(xiàn)在我們假設(shè)4、5围段、6號(hào)也進(jìn)行了一番幫派合并顾翼，江湖局勢(shì)變成下面這樣：
現(xiàn)在假設(shè)2號(hào)想與6號(hào)比，跟剛剛說(shuō)的一樣奈泪，喊幫主1號(hào)和4號(hào)出來(lái)打一架（幫主真辛苦氨┕埂）。1號(hào)勝利后段磨，4號(hào)認(rèn)1號(hào)為幫主取逾，當(dāng)然他的手下也都是跟著投降了。
好了苹支，比喻結(jié)束了砾隅。如果你有一點(diǎn)圖論基礎(chǔ)，相信你已經(jīng)覺(jué)察到债蜜，這是一個(gè)樹狀的結(jié)構(gòu)晴埂，要尋找集合的代表元素，只需要一層一層往上訪問(wèn)父節(jié)點(diǎn)（圖中箭頭所指的圓）寻定，直達(dá)樹的根節(jié)點(diǎn)（圖中橙色的圓）即可儒洛。根節(jié)點(diǎn)的父節(jié)點(diǎn)是它自己。我們可以直接把它畫成一棵樹：
用這種方法狼速，我們可以寫出最簡(jiǎn)單版本的并查集代碼琅锻。
最簡(jiǎn)單的并查集
存儲(chǔ)結(jié)構(gòu)
class UnionFind {
int[] parent;
}
初始化
假如有編號(hào)為1, 2, 3, ..., n的n個(gè)元素，我們用一個(gè)數(shù)組parent[]來(lái)存儲(chǔ)每個(gè)元素的父節(jié)點(diǎn)（因?yàn)槊總€(gè)元素有且只有一個(gè)父節(jié)點(diǎn)向胡，所以這是可行的）恼蓬。一開始，我們先將它們的父節(jié)點(diǎn)設(shè)為自己僵芹。
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
查詢
我們用遞歸的寫法實(shí)現(xiàn)對(duì)代表元素的查詢：一層一層訪問(wèn)父節(jié)點(diǎn)处硬，直至根節(jié)點(diǎn)（根節(jié)點(diǎn)的標(biāo)志就是父節(jié)點(diǎn)是本身）。要判斷兩個(gè)元素是否屬于同一個(gè)集合拇派，只需要看它們的根節(jié)點(diǎn)是否相同即可荷辕。
public int find(int x) {
if (parent[x] == x) {
return x;
} else {
return find(parent[x]);
}
}
合并
合并操作也是很簡(jiǎn)單的凿跳，先找到兩個(gè)集合的代表元素，然后將前者的父節(jié)點(diǎn)設(shè)為后者即可疮方。當(dāng)然也可以將后者的父節(jié)點(diǎn)設(shè)為前者拄显，這里暫時(shí)不重要。本文末尾會(huì)給出一個(gè)更合理的比較方法案站。
public void merge(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) {
return;
}
parent[i] = j;
}
一個(gè)簡(jiǎn)單的并查集功能就完成了, 試一下
/**
* 判斷節(jié)點(diǎn)x和節(jié)點(diǎn)y是不是有聯(lián)系
*
* @param n 節(jié)點(diǎn)數(shù)量
* @param connections 節(jié)點(diǎn)間關(guān)系 : 例子 connections[i] = [a, b] 表示 a 和 b 是親戚躬审。
* @param x 節(jié)點(diǎn)x
* @param y 節(jié)點(diǎn)y
* @return x和節(jié)點(diǎn)y是不是有聯(lián)系
*/
public boolean makeConnected(int n, int[][] connections, int x, int y) {
UnionFind uf = new UnionFind(n);
for (int[] conn : connections) {
uf.merge(conn[0], conn[1]);
}
return uf.find(x) == uf.find(y);
}
改進(jìn)
路徑壓縮
最簡(jiǎn)單的并查集效率是比較低的。例如蟆盐，來(lái)看下面這個(gè)場(chǎng)景：
現(xiàn)在我們要merge(2,3)承边，于是從2找到1，parent[1]=3石挂，于是變成了這樣：
然后我們又找來(lái)一個(gè)元素4博助，并需要執(zhí)行merge(2,4)：
從2找到1，再找到3痹愚，然后fa[3]=4富岳，于是變成了這樣：
大家應(yīng)該有感覺(jué)了，這樣可能會(huì)形成一條長(zhǎng)長(zhǎng)的鏈拯腮，隨著鏈越來(lái)越長(zhǎng)窖式，我們想要從底部找到根節(jié)點(diǎn)會(huì)變得越來(lái)越難。
怎么解決呢动壤？我們可以使用路徑壓縮的方法萝喘。既然我們只關(guān)心一個(gè)元素對(duì)應(yīng)的根節(jié)點(diǎn)，那我們希望每個(gè)元素到根節(jié)點(diǎn)的路徑盡可能短琼懊，最好只需要一步阁簸，像這樣：
其實(shí)這說(shuō)來(lái)也很好實(shí)現(xiàn)。只要我們?cè)诓樵兊倪^(guò)程中哼丈，把沿途的每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都設(shè)為根節(jié)點(diǎn)即可启妹。下一次再查詢時(shí)，我們就可以省很多事醉旦。這用遞歸的寫法很容易實(shí)現(xiàn)：
合并（路徑壓縮）
public int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
按秩合并
有些人可能有一個(gè)誤解饶米，以為路徑壓縮優(yōu)化后，并查集始終都是一個(gè)菊花圖（只有兩層的樹的俗稱）髓抑。但其實(shí)咙崎，由于路徑壓縮只在查詢時(shí)進(jìn)行优幸，也只壓縮一條路徑吨拍，所以并查集最終的結(jié)構(gòu)仍然可能是比較復(fù)雜的。例如网杆，現(xiàn)在我們有一棵較復(fù)雜的樹需要與一個(gè)單元素的集合合并：
假如這時(shí)我們要merge(7,8)羹饰，如果我們可以選擇的話伊滋，是把7的父節(jié)點(diǎn)設(shè)為8好，還是把8的父節(jié)點(diǎn)設(shè)為7好呢队秩？
當(dāng)然是后者笑旺。因?yàn)槿绻?的父節(jié)點(diǎn)設(shè)為8，會(huì)使樹的深度（樹中最長(zhǎng)鏈的長(zhǎng)度）加深馍资，原來(lái)的樹中每個(gè)元素到根節(jié)點(diǎn)的距離都變長(zhǎng)了筒主，之后我們尋找根節(jié)點(diǎn)的路徑也就會(huì)相應(yīng)變長(zhǎng)。雖然我們有路徑壓縮鸟蟹，但路徑壓縮也是會(huì)消耗時(shí)間的乌妙。而把8的父節(jié)點(diǎn)設(shè)為7，則不會(huì)有這個(gè)問(wèn)題建钥，因?yàn)樗鼪](méi)有影響到不相關(guān)的節(jié)點(diǎn)藤韵。
這啟發(fā)我們：我們應(yīng)該把簡(jiǎn)單的樹往復(fù)雜的樹上合并，而不是相反熊经。因?yàn)檫@樣合并后泽艘，到根節(jié)點(diǎn)距離變長(zhǎng)的節(jié)點(diǎn)個(gè)數(shù)比較少。
我們用一個(gè)數(shù)組rank[]記錄每個(gè)根節(jié)點(diǎn)對(duì)應(yīng)的樹的深度（如果不是根節(jié)點(diǎn)镐依，其rank相當(dāng)于以它作為根節(jié)點(diǎn)的子樹的深度）匹涮。一開始，把所有元素的rank（秩）設(shè)為1槐壳。合并時(shí)比較兩個(gè)根節(jié)點(diǎn)焕盟，把rank較小者往較大者上合并机错。路徑壓縮和按秩合并如果一起使用消玄，時(shí)間復(fù)雜度接近 [圖片上傳失敗...(image-98c7ec-1611629139843)] ，但是很可能會(huì)破壞rank的準(zhǔn)確性炎咖。
存儲(chǔ)結(jié)構(gòu)
class UnionFind {
int[] parent;
int[] rank;
}
初始化（按秩合并）
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
rank = new int[n];
Arrays.fill(rank, 1);
}
合并（按秩合并）
public void merge(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) {
return;
}
if (rank[i] > rank[j]) {
parent[j] = i;
} else {
parent[i] = j;
}
if (rank[i] == rank[j]) {
rank[i]++;
}
}
為什么深度相同绍哎，新的根節(jié)點(diǎn)深度要+1来农？如下圖，我們有兩個(gè)深度均為2的樹崇堰，現(xiàn)在要merge(2,5)：
這里把2的父節(jié)點(diǎn)設(shè)為5沃于，或者把5的父節(jié)點(diǎn)設(shè)為2，其實(shí)沒(méi)有太大區(qū)別海诲。我們選擇前者繁莹，于是變成這樣：
顯然樹的深度增加了1。另一種合并方式同樣會(huì)讓樹的深度+1特幔。
解題 連通網(wǎng)絡(luò)的操作次數(shù)
public class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) {
return -1;
}
UnionFind uf = new UnionFind(n);
for (int[] conn : connections) {
uf.merge(conn[0], conn[1]);
}
return uf.outlierNum - 1;
}
}
class UnionFind {
int[] parent;
int[] rank;
int outlierNum;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
rank = new int[n];
Arrays.fill(rank, 1);
outlierNum = n;
}
public int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
public void merge(int x, int y) {
int i = find(x);
int j = find(y);
if (i == j) {
return;
}
if (rank[i] > rank[j]) {
parent[j] = i;
} else {
parent[i] = j;
}
if (rank[i] == rank[j]) {
rank[i]++;
}
outlierNum--;
}
}
