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