解题思路

核心建模

给定的 n×n 网格是无向图的邻接矩阵：grid[i][j]='1' 表示歌曲 i 与 j 有边。题目等价于：在无向图中统计连通分量的个数。

题目内容

给定一个由 $'1’$ (有关系)和 $'0'$ (无关系)组成的二维网格，该网格是一个 $n×n$ 的邻接矩阵( $n$ 为歌曲数量)，其中 $grid[i][j]:'1'$ 表示歌曲 $i$ 和歌曲 $j$ 存在直接关系，$grid[i][j]='0'$ 表示两首歌曲无直接关系。

歌曲簇的定义：由直接或间接存在关系的歌曲组成的集合(例如：若歌曲 $A$ 与 $B$ 有关系，$B$ 与 $C$ 有关系，则 $A、B、C$ 属于同一个簇)。

请计算该网格中歌曲簇的数量。

说明：

关系具有双向性：若歌曲 $i$ 与 $j$ 有关系$(grid[i][j]='1')$，则歌曲 $j$ 与 $i$ 也一定有关系 $(grid[i][j] ='1')$ 。

网格的边界外不存在其他歌曲(无需考虑边界外的关系)。

输入描述

$n == grid.length == grid [i].ength$ (网格为 $n$ 阶方阵)

$1 <= n <= 300$

$grid [i][j]$ 的值为 $'0'$ 或 $'1'$

输出描述

输出一个整数，表示歌曲簇数量

样例1

输入

[['1', '1'],['1', '1']]

输出

1