從LeetCode學演算法-120 (0547. Number of Provinces)

Categories: Graph/Union Find, Level: Medium

寫在前面： (基礎+進階+面試篇)從 LeetCode 學演算法 + 面試成功指南

(3591元 特價中: 2023/06/30 23:59後截止) https://hiskio.com/bundles/eCP23B397?s=tc

(3990元 長期有效) https://bit.ly/lc2022all

容筆者工商一下， 「從Leetcode學演算法｜進階篇」這次選了40道難度加深的LeetCode題目， 同樣也會細部解說對應的技巧及須要掌握的演算法！ 同時這次購買進階篇的話， 額外還加贈「從Leetcode學演算法｜面試篇」！ 當中包含了面試準備須知分享，及訪談國內外不同經驗的工程師， 讓你不論是想走前端/後端/一般軟工或者是想找國外的工作， 是初學想轉職還是正在工作，都能夠從中得到收穫呦！ 有興趣的朋友可以使用下面的優惠～ 「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」： https://bit.ly/lc2022adv

請幫我隨手點開下面的SHOW EMBED並按5個like～ 喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)

Question:

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

分析/解題：

有n個城市，其中一些城市彼此相連，而另一些則沒有。 如果城市a與城市b直接相連，並且城市b與城市c直接相連， 那麼城市a與城市c之間間接相連。(OS: 好廢話XD)

一個省(province)是一組直接或間接相連的城市， 且該群組中沒有其他的城市。 (也就是直要可以從x走到y，它們就視為相同省)

給定一個n x n的矩陣isConnected， 其中isConnected[i][j] = 1表示第i個城市和第j個城市直接相連，isConnected[i][j] = 0則表示它們不直接相連，回傳省的總數量。

我們已經在第115篇以及上一篇中提到了很多Graph的概念， 今天再來仔細一點探討Union Find的用法。

由於isConnected太長了，我們底下還是直接使用edges來稱呼比較簡便。 首先看到了要找provinces的組數， 顯然又是一個很典型能使用Union Find的場合； 但先前我們提到過，如果只是一路沿著edge往回trace老大的話， 對於單一點的find有可能達到O(n)， 因此我們需要做一些簡化：在union的合併時， 就盡可能地先行收斂。那麼我們應該怎麼做呢？

我們這邊定義一個串列叫做rank， 用以表達每個節點往上對到的root所含有的節點總數。 那麼在合併的時候，有別於先前的任意指定， 我們這次可以選擇先檢查誰的rank大， 接著人多欺負人少......不對，是rank大的合併掉rank小的群組； rank小的群組的root要設定為rank大的群組的root。 這麼一來，在合併的過程中，由於一直是大的合併小的， 相對而言會較不容易將union的連接拉太多層， 這個手法我們稱之為路徑壓縮(path compression)。

因此，我們的find的寫法和union的寫法會像這樣： find(root, i): 1. 先取到r = root[i] 2. 如果r和root[r]不相等(代表還沒走到自己是root(老大)的節點)進行迴圈: 3. 將root[root[r]]的值塞給root[r] 4. 令r = root[r] (來到上面一層，繼續準備判斷) 5. 在2~4的迴圈結束後，直接令root[i] = r， 標明節點i的最上面的老大是r。

union(root, rank, x, y): 1. 對x, y分別使用find，取得各自的root rx, ry 2. 如果rx和ry相同，代表已經是同一組了，直接回傳false 3. 如果不同，則看rank[rx]和rank[ry]的關係， rank[rx] ≥ rank[ry]的話，就將rank[rx]遞增rank[ry]， 並且令root[ry] = rx； 反之，若rank[rx] < rank[ry]，則將rank[ry]遞增rank[rx]， 並且令root[rx] = ry。

那麼，剩下來我們只需要做完對root和rank的初始化(1~n-1跟1) 剩下就是雙層迴圈對有edge的兩點呼叫union， 最後對於每個節點確認它們不重複的root有哪些即可。

依此，寫成程式碼如下：

Java:

Java的部分一樣可以用Arrays.fill()來設定定值， 同時因為我們union其實沒特別用到true/false的需求， 可以設定為void，直接將對應該改的東西改一改， 並直接return即可。

同時，在記錄答案時，我們可以使用HashSet， 在最後對i做遍歷並逐個進行find()，並加到當中， 最後檢查res.size()即可得到我們要的答案。

另外可以留意的是，雙重迴圈的union(i, j)因為沒有方向性的關係， 第二層的j可以從i+1開始就好，不需要從0開始。

Python:

Python的部分除了改成用子函式以外， 其餘則大同小異。

面試實際可能會遇到的問題： 「時間/空間複雜度？」 ( O(n²)/O(n)，因為即便有經過path的壓縮，遍歷所有edge仍然要O(n²)， 空間的部分則是只需要考慮記錄root和rank的空間)

相似及延伸： 0684. Redundant Connection (Medium)

Special Thanks suggestions/corrections from viewers: (歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？ 歡迎從第零篇找你想要的！

同時追蹤粉專以獲得更多新文章的通知： 跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」已經回原價囉， 先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵， 雖然整捆一起買總體比較划算(差290而已就有整組了阿XD)， 如果你還是想先試試基礎課的話， 300元折抵的連結在這邊： https://bit.ly/lc2022base

如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。