Problem6943--省份数量

6943: 省份数量

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有 $n$ 个城市,其中一些彼此相连,另一些没有相连。
如果城市 $a$ 与城市 $b$ 直接相连,且城市 $b$ 与城市 $c$ 直接相连,那么城市 $a$ 与城市 $c$ 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

Input

第一行包括两个正整数 $n\ (1 \leq n \leq 200)$,$n$ 表示城市数量。
第 $2 \sim n+1$ 行,每行包括 $n$ 个整数。$1$ 表示城市 $i$ 和城市 $j$ 相连,$0$ 表示城市 $i$ 和城市 $j$ 不相连。

Output

返回矩阵中 省份 的数量。

Sample 1 Input

3
1 1 0
1 1 0
0 0 1

Sample 1 Output

2

Sample 2 Input

3
1 0 0
0 1 0
0 0 1

Sample 2 Output

3

HINT

相同题目:LeetCode

Source/Category