题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

题解

  1. 访问一个点A，遍历其他点和A点有没关联，有关联并且没有访问过，就换成访问这个点B和其他没有访问过的点的关联
  2. 访问完一个点的群后，继续访问下一个没有访问的过的点，直到所有点访问完。

后知后觉，这就是dfs啊

code

有点难度

  1. class Solution:
  2.     def findCircleNum(self, isConnected: List[List[int]]) -> int:
  3.         n = len(isConnected)
  4.         records = set()
  5.         def visitPoint(i):
  6.             for j in range(n):
  7.                 if isConnected[i][j] == 1 and j not in records:
  8.                     records.add(j)
  9.                     visitPoint(j)
  10.         count = 0
  12.         for i in range(n):
  13.             if i not in records:
  14.                 count+=1
  15.                 visitPoint(i)
  17.         return count