https://leetcode.com/problems/number-of-provinces/description/
547. Number of Provinces
給你一個陣列isConnected[][],isConnected[i][j] 表示第 i 個城市是否與第 j
個城市相連(1表示相連),一個直接或間接相連的城市集合為一個省份,找出這個圖
共有幾個省。
Example 1:
https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Example 2:
https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
思路:
1.從隨便一個點出發並遍歷所有相鄰的點(DFS),每次遇到沒走過的城市時省分數量+1,
走過的城市用一個visited[]標記已經走過,下次遇到就跳過。
2.遍歷完整個陣列返回統計的省分數量。
Java Code: