P1388. 枢纽节点问题

描述

几十年来，人们已经认识到数据通信的重要性。通信网络的大多数设计和分析通常将其拓扑结构建模为图形表示，因为网络的许多相关问题可以通过使用图论结果来解决。通常，一个通信网络被建模为一个图，图中的节点和边分别对应通信站点和链路。一个网络$G = (N, E)$由一组节点$N$和一组边$E$组成，边表示节点对。如果这些节点对被认为是无序的，那么我们就有一个无向网络，连接两个节点$u$和$v$的边用$(u, v)$表示。例如，图 3 描绘了一个包含 10 个节点和 16 条边的网络$G$。

在一个网络$G$中，两个节点$u$和$v$之间的距离，用$d_G(u, v)$表示，是$G$中从$u$到$v$的最短路径的边数。顶点序列$v_1, v_2, \cdots, v_k$是$G$中从$v_1$到$v_k$长度为$k - 1$的路径，条件是对于$i = 1, 2, \cdots, k - 1$，在$v_i$和$v_{i + 1}$之间有一条边。如果节点$u$和$v$之间不存在路径，那么$d_G(u, v) = \infty$。如果路径的长度在$u$和$v$之间的所有路径中是最小的，那么该路径就是$u$和$v$之间的最短路径。如果任意两个节点之间都存在路径，那么这个网络是连通的。节点$w$的失效意味着$w$及其所有关联边都从$G$中移除，剩余的子网络表示为$G - w$。节点$w$被称为枢纽节点，如果在$G$中存在另外两个节点$u$和$v$，使得$d_{G - w}(u, v) > d_G(u, v)$。这意味着在节点$w$从$G$中移除后，$u$和$v$之间的距离增加了。因此，枢纽节点可以被视为相应网络的关键节点，这样的节点失效会增加剩余子网络的通信成本。例如，我们考虑图 3 中的网络$G$。节点$v_2$是一个枢纽节点，因为$d_{G - v_2}(v_8, v_9) = 3 > d_G(v_8, v_9) = 2$。实际上，$G$中包含的枢纽节点集合是$\{v_2, v_3, v_4, v_7, v_8, v_{10}\}$。

假设我们有几个网络。每个网络都是连通的，并且最多包含$n$个节点，其中$3 \leq n \leq 100$。现在假设你被聘请为网络管理员，你应该分析通信成本。因此，你会对找到给定网络中的所有枢纽节点感兴趣。特别地，你应该设计一个程序，能够有效地计算每个给定网络中枢纽节点的总数。

输入

输入文件包含多于一个且少于六个网络（案例）。每个测试用例以一个正整数$n$开始，其中$3 \leq n \leq 100$。接下来的$n$行表示一个网络$G$的邻接矩阵。最后一个案例后面跟着一个“0”，表示“输入结束”。一个具有$n$个节点的网络$G$的邻接矩阵，用$A(G) = [a_{u, v}]$表示，是一个$n \times n$的$0, 1$矩阵，使得如果$(u, v) \in E$，则$a_{u, v} = 1$，否则$a_{u, v} = 0$。注意，在$0, 1$矩阵的每一行中，任意两个元素之间没有分隔符。例如，图 3 中图形的邻接矩阵如示例输入的测试用例 3 所示。

输出

对于每个测试用例，在一行中输出枢纽节点的总数。

输入数据 1

3
010
101
010
3
011
101
110
10
0110001000
1001000111
1000001100
0100010101
0000000101
0001000001
1010000010
0111100000
0100001000
0101110000
0 

输出数据 1

1
0
6 

来源

台湾 2001