從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

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

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

Example 2

1
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):

先取到r = root[i]
如果r和root[r]不相等(代表還沒走到自己是root(老大)的節點)進行迴圈:
將root[root[r]]的值塞給root[r]
令r = root[r] (來到上面一層，繼續準備判斷)
在2~4的迴圈結束後，直接令root[i] = r，
標明節點i的最上面的老大是r。

union(root, rank, x, y):

對x, y分別使用find，取得各自的root rx, ry
如果rx和ry相同 ，代表已經是同一組了，直接回傳false
如果不同，則看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的空間)

相似及延伸

Redundant Connection (Medium)

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

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

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

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

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