經典圖論應用: 省分的總數目 Number of Provinces_Leetcode #547_精選75題

Hans Isaacson on Unsplash

題目敘述

題目會給我們一串相鄰矩陣isConnected，相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。

如果彼此有連通，則isConnected[i][j]=1。

如果彼此沒有連通，則isConnected[i][j]=0。

彼此互相有路徑可以抵達的城市，構成一個省份。

請問，在輸入的場景中，省分的總數目是多少？

題目的原文敘述

測試範例

Example 1:

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

1號2號構成第一個省份。
3號構成第二個省份。

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
1號自己構成第一個省份。
2號自己構成第二個省份​。
3號自己構成第三個省份​。

約束條件

Constraints:

• 1 <= n <= 200

城市總數目介於1 ~ 200之間。

• n == isConnected.length

輸入矩陣isConnected的高是n。

• n == isConnected[i].length

輸入矩陣isConnected的寬是n。

結合上面那點一起看，代表isConnected是一個n * n 的方陣。

• isConnected[i][j] is 1 or 0.

元素值要嘛是1，要嘛是0。

• isConnected[i][i] == 1