前往
大廳
主題

LeetCode - 547. Number of Provinces 解題心得

Not In My Back Yard | 2022-08-17 12:00:11 | 巴幣 0 | 人氣 339

題目連結:


題目意譯:
現在有 n 座程式。其中有些是連通的,而有些則沒有。如果城市 a 與城市 b 有直接連通,而且城市 b 與城市 c 也有直接連通,則城市 a 與城市 c 將間接地連通。

一個省為一群直接或間接地連通之城市而且沒有其他不屬於該群體的城市存在。

你被給定一個 n × n 矩陣 isConnected,其中 isConnected[i][j] = 1 如果第 i 座城市與第 j 座城市有直接連通;反之,isConnected[i][j] = 0。

回傳省的總數。

限制:
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]



範例測資:
範例 1:
輸入: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出: 2

範例 2:
輸入: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出: 3


解題思維:
基本上與我在若干年前寫的小說題目雷同。只是本題是直接給你每個城市之間的關係,而不是每座城市通到哪幾座城市(因此會少了一些前置處理)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作