问题 3351 --连通数

3351: 连通数

时间限制: 1 Sec  内存限制: 256 MB
提交: 4  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

度量一个有向图连通情况的一个指标是连通数,指图中可达顶点对个的个数。

如图

顶点 1 可达 1,2,3,4,5

顶点 2 可达 2,3,4,5

顶点 3 可达 3,4,5

顶点 4,5 都只能到达自身。

所以这张图的连通数为 14

给定一张图,请你求出它的连通数

输入

输入数据第一行是图顶点的数量,一个正整数 N
接下来 N 行,每行 N 个字符。第 i 行第 j 列的 1 表示顶点 i 到 j 有边,0 则表示无边。

输出

输出一行一个整数,表示该图的连通数。

样例输入

3
010
001
100

样例输出

9

提示

对于 100% 的数据,1N2000

来源

[提交][状态]