Ex8-4 汇点问题

« 问题描述：

采用邻接矩阵表示一个具有n 个顶点的图时，大多数关于图的算法时间复杂性为

O(n2 )，但也有例外。例如，即使采用邻接矩阵表示一个有向图G，确定G 是否含有一个

汇（即入度为n-1，出度为0 的顶点），只需要O(n)计算时间。试写出其算法。

« 编程任务：

对于给定的有n个顶点的图G 的邻接矩阵，各顶点依次编号为1，2，…，n。试设计一

个O(n)时间算法，计算图G 的汇点。

« 数据输入：

由文件input.txt提供输入数据。文件的第1 行有1 个正整数n，表示图G 中顶点个数。

第2 行起每行n个数，共n行，给出图G 的邻接矩阵。

« 结果输出:

程序运行结束时，将计算出的汇点编号输出到output.txt中。当图G 没有汇点时输出0。

输入文件示例 输出文件示例

input.txt

5

0 0 1 1 1

1 0 1 1 1

0 0 0 0 0

1 0 1 1 1

0 1 1 0 0

output.txt

3