547. Number of Provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
DFS搜索,当map[i][i] = 1时加入搜索。
搜索时将map[i][i]设为0。遍历并递归其数列。
当map[i][i]等于0时,返回。
1 | class Solution { |
547. Number of Provinces
https://xuanhe95.github.io/2022/04/21/547-Number-of-Provinces/