algorithm - 如何在O(n)时间内求和邻接矩阵的列

Question

有向图的n x n邻接矩阵我想搜索一下是否有任何列的总和为n。问题是我必须在O（n）时间内完成这项工作有没有办法在O（n）时间内解决这个问题，或者不可能（不需要代码）？
作为参考，下面是我试图解决的问题：
问题：
在学校的乐队成员选举中，每个人对总统都有一些偏好，对一个人的偏好包括他/她所有的时间“完美的”总统是指在每个人的偏好中，除了他/她自己之外，不喜欢任何人的人。我们只想知道这样的人是否存在。
定义一个有向图，当且仅当b在a的首选项集中时，候选集为顶点，且从顶点a到顶点b的有向边。
有N个人
我们需要一个在o（n）时间内执行的算法
我们以n x n邻接矩阵的形式给出了上面描述的图。
我想，如果每个人都投“完美总统”的票，那么他/她将有N个新的节点，因此对这个列进行总结应该会给我们N个。如果有更好的方法来解决这个问题，而不是像我这样做，任何提示都会引导我朝着正确的方向前进。

Answer 1

让我重复一下规则并给它们编号，以便于参考：
都喜欢自己
所有人都喜欢完美的总统（如果有的话）
完美的总统（如果有的话）不喜欢别人
让我们定义邻接矩阵，这样当person i偏好person j时，行i和列j中的值为1。所有其他值都为0。
以上三条规则可以根据邻接矩阵重新表述如下：
邻接矩阵的主对角线都是1。
如果完美的总统是第一，那么第一栏就全是1。
如果完美的总统是一号，那么除第一列外，第一行的总统都是0。
请注意，不能有两个或两个以上的完美总统，因为这样他们就不得不彼此偏爱（规则2），这违反了规则3。
算法：曲折相位
完美的总统（如果存在）可以在线性时间中找到，根据邻接矩阵左上角的Zig-Zigg（行0，列0），根据以下规则：
如果值为1，则下移到下一行（同一列）
如果值为0，则向右移动到下一列（同一行）
在保持矩阵边界内的同时，继续重复前两个步骤。
如果退出矩阵，此阶段结束。让我们调用该列，在那里我们退出矩阵，列p。
观察：由于规则1，算法的这一部分永远不会进入主对角线上方的值：该对角线上的1-值就像一面墙，每当我们碰到它时，它就会把我们向下推。因此，您总是从最后一行向下移动，退出矩阵。在最极端的情况下，在矩阵的右下角（对角线上）的1处向下移动。
下面是一个简单的邻接矩阵示例，其中箭头指示算法如何指示从左上角到下一行某处1的路径：

 1   1   0   1   0
 ↓
 1   1   0   1   0
 ↓
 0 → 1   1   1   0 
     ↓
 0   0 → 0 → 1   0
             ↓
 0   1   1   1   1
             ↓
            =p

注意，在这个例子中有一个完美的总统，但这当然不是一个要求：无论是否有一个完美的总统，算法都会给你一个p值。
声明：完美的总统，如果有的话，必须是p号的人。
证明
给定的是由上述之字形算法返回的p。
首先，我们矛盾地证明：
a）完美的总统不能是一个数字i小于p的人。
所以让我们假设相反：完美的总统是我和我因为我们在第0列开始了曲折阶段，最后进入了第p列，而且在这个过程中我们不能跳过一列，所以有一瞬间我们进入了第一列。因为我们没有停留在那个列中，这一定意味着第i列的一行中有一个0，它调用我们向右移动但规则2要求，如果我是一个完美的总统，专栏i应该只有1个值（规则2）矛盾！
其次，我们矛盾地证明：
b）完美的总统不能是一个数字i大于p的人。
所以让我们假设相反：完美的总统是我和P：
由于我们在第0行开始了锯齿形阶段，并且到达了最后一行（参见观察结果），并且在这个过程中我们不能跳过一行，所以有一瞬间我们进入了第一行。由于我们没有停留在那一行，而是在某个点向下移动（参见观察结果：我们向下移动离开矩阵），这一定意味着第一行有一个1在它的一根柱子上，它叫我们向下移动。这个1不能是对角线上的1（在[i，i]），因为我们没有到达列i:i大于p，算法结束于列p。所以它一定是第i行中的另一个1，第二个1。
但是规则3要求如果我是一个完美的总统，row i应该只有一个1值，所有其他值都是零。矛盾！
这两个矛盾的证明给我们留下了完美总统的唯一可能数，如果有的话，就是p。
算法：验证阶段
实际上检查p是否真的是一个完美的总统是很简单的：我们只需要检查p列是否包含所有的1，而p行只包含0，除了i列。
时间复杂性
所有这些都可以在线性时间内完成：在锯齿形阶段，最多需要从矩阵中读取2n-1，在最终验证阶段，最多需要读取2n-2。因此这是o（n）。