城市群数量_牛客题霸

给定一个 n 个节点的邻接矩阵 m。节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。请你找出共有多少个城市群。数据范围：，矩阵中只包含和

示例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属于一个城市群。