城市群数量

[编程题]城市群数量

热度指数：1534 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 个节点的邻接矩阵 m。节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。

矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。

请你找出共有多少个城市群。

数据范围： $1 \le n \le 200 \$ ，矩阵中只包含 $0 \$ 和 $1 \$

示例1

输入

[[1,1,0],[1,1,0],[0,0,1]]

输出

说明

1 2 相连，3 独立，因此是 3 个城市群。

示例2

输入

[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

输出

说明

1 ， 2相连 ；2 ，3相连，4独立，因此是 1,2,3 属于一个城市群，4属于一个城市群。

算法知识视频讲解

Python3

牛客808686245号

class Solution:
    map=[]
    def citys(self , m: List[List[int]]) -> int:
        num=0
        self.map=[0]*len(m)
        for i in range(len(m)):
            if self.map[i]==0:
                num+=1
                self.dfs(i,m)
        return num

    def dfs(self,x,m):
        self.map[x]=1
        for i in range(len(m[x])):
            if m[x][i]==1 and self.map[i]==0:
                self.dfs(i,m)

发表于 2022-09-24 16:49:28 回复(0)