极大连通子图的个数

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int: 
        n = len(isConnected)
        visited =set() # 使用列表可以减小一点开销
        cnt =0
        def dfs(pos):
            for i in range(n):  # 对该城市搜索所有相邻城市
                if isConnected[pos][i] and i not in visited :
                    visited.add(i)
                    dfs(i)
        for i in range(n): # 开始遍历所有城市
           if i not in visited: # 开始时也会加一个判断是否访问过
                dfs(i)  # 如果没有访问则进行深度优先搜索，将其相邻城市标记为访问
                cnt+=1
        return cnt

Warshall 算法通过求可达矩阵，对上三角进行遍历

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int: 
        n = len(isConnected)

        for j in range(n):
            for i in range(n):
                if isConnected[i][j]==1:
                    for k in range(n):
                        isConnected[i][k]|= isConnected[j][k]
        cnt=0
        for i in range(n):
            flag =0 
            if isConnected[i][i]==0:continue
            for j in range(i,n):
                if  isConnected[i][j]==1:
                    isConnected[j][j]=0
                    if not flag:
                        cnt+=1
                        flag=1
        return cnt