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: