Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-06-04 22:12:18
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:
作者: a9486l (a9486l)   2022-06-04 22:12:00
大师
作者: JIWP (JIWP)   2022-06-04 22:12:00
大师
作者: MinatoKomugi (凑小麦)   2023-06-04 22:13:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com