目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

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

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

二、解题思路

p存储每个节点的对应连通的起始节点；

按行遍历矩阵的下三角，只要为1且p中当前城市i的值和本该连接的城市j的值不同，则当前城市i的值被赋值为本该连接城市j的值；

例如4个城市，124相连的话，则[0, 1, 2, 3]=>[0, 0, 2, 3]=>[0, 0, 2, 0]， 意思是4和2连着，而2和1连着，则4和1连着，因此这三个城市的值都为0；

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def findCircleNum(self, isConnected: list) -> int:
     
    
   

    

     

    
    

     

       p = [i for i in range(len(isConnected))]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def find(x):
     
    
   

    

     

    
    

     
 if p[x] != x:
     
    
   

    

     

    
    

     

       p[x] = find(p[x])
     
    
   

    

     

    
    

     
 return p[x]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       res = len(isConnected)
     
    
   

    

     

    
    

     
 for i in range(len(isConnected)):
     
    
   

    

     

    
    

     
 for j in range(i):
     
    
   

    

     

    
    

     
 # print(i, j)
     
    
   

    

     

    
    

     
 if isConnected[i][j] == 1 and find(i) != find(j):
     
    
   

    

     

    
    

     
 # print(i, j)
     
    
   

    

     

    
    

     
 # print(find(i), find(j))
     
    
   

    

     

    
    

     

       p[find(i)] = find(j)
     
    
   

    

     

    
    

     

       res -= 1
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       isConnected = [[1, 1, 0, 0],
     
    
   

    

     

    
    

     

       [1, 1, 0, 1],
     
    
   

    

     

    
    

     

       [0, 0, 1, 0],
     
    
   

    

     

    
    

     

       [0, 1, 0, 1]]
     
    
   

    

     

    
    

     

       ans = s.findCircleNum(isConnected)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/112304839