如何在 O(n) 时间内对邻接矩阵的列求和
How to sum columns of an adjacency matrix in O(n) time
我有一个有向图的 n x n 邻接矩阵。我想搜索以查看是否有任何列总和为 n。问题是我必须在 O(n) 时间内完成此操作。有什么方法可以用 O(n) 时间来解决这个问题，还是不可能（不需要代码）？
作为参考，下面是我试图解决的问题：
问题：
During the school bandmates election, each person has a few preferences for the president and the set of preferences for a person includes him/herself all the time. The "perfect" president is the one who is in the set of preferences of every person and who does not prefer anyone but him/herself. All we want to know is whether such a person exists or not.
- Define a directed graph with the set of candidates as the vertices and a directed edge from vertex a to vertex b if and only if b is in the set of preferences of a.
- There are n people
- We want an algorithm which executes in O(n) time
- We are given the graph described above in the form of an n x n adjacency matrix
我认为如果每个人都投票给“完美总统”，那么 he/she 将有 n 个传入节点，因此对列求和应该给我们 n。如果有比我现在做的更好的方法来解决这个问题，任何提示都将不胜感激，以指导我朝着正确的方向前进。
让我重复一下规则并给它们编号以便于参考：
- 都喜欢自己
- 所有人都喜欢完美的总统（如果有的话）
- 完美总统（如果有的话）不会偏爱任何人
让我们定义邻接矩阵，使得行 i 和列 j 的值在 i 时为 1 对 j 有偏好。所有其他值为 0。
以上三个规则可以根据邻接矩阵重新表述如下：
- 邻接矩阵的主对角线全为 1。
- 如果完美总统是数字i，那么第i列将全为1。
- 如果完美总统是数字 i，那么第 i 行将全为 0，第 i 列除外.
请注意，不能有两个或两个以上的完美总统，因为那样他们就必须互相偏爱（规则 2），这违反了规则 3。
算法：锯齿形阶段
完美总统（如果存在）可以在线性时间内找到，从邻接矩阵（第 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号的人。
证明
给定的是上述zig-zag算法返回的p。
首先我们用反证法证明：
a) 完美总统不能是i小于p.
的人
所以让我们假设相反：完美的总统是 i 并且 i < p:
由于我们在第 0 列开始锯齿形阶段并在第 p 列结束，并且由于在此过程中我们不能跳过任何一列，所以有一段时间我们在 i 列中。由于我们没有留在该列中，这一定意味着列 i 的其中一行中有一个零，这要求我们向右移动。但是规则 2 要求如果 i 是一位完美的总统，则 i 列应该只有 1 个值（规则 2）。矛盾！
其次我们用反证法证明：
b)完美总统不可能是i大于p.
的人
所以让我们假设相反：完美的总统是 i 并且 i > p:
由于我们在第 0 行开始锯齿形阶段并到达最后一行（参见观察），并且由于在此过程中我们不能跳过一行，所以有一段时间我们在行 我。由于我们没有留在那一行，而是在某个点向下移动（参见观察：我们向下移动移出矩阵），这一定意味着行 i其中一列中有一个 1，它要求我们向下移动。这个 1 不能是对角线上的 1（在 [i,i]），因为我们没有到达第 i 列：i 大于 p 并且算法在列 p 结束。所以它一定是另一个 1，第二个，在行 i.
但是规则 3 要求如果 i 是一位完美的总统，行 i 应该只有一个 1 值，所有其他值为零。矛盾！
这两个矛盾的证明给我们留下了完美总统的其他可能数字，如果有的话，除了 p。
算法：验证阶段
要实际检查人 p 是否确实是一位完美的总统是微不足道的：我们可以检查列 p 是否包含全 1， p 行仅包含 0，i.
列除外
时间复杂度
所有这些都可以在线性时间内完成：zig-zag阶段最多需要2n-1次矩阵读取，而2n- 2 更多在最后的验证阶段。因此这是 O(n).
我有一个有向图的 n x n 邻接矩阵。我想搜索以查看是否有任何列总和为 n。问题是我必须在 O(n) 时间内完成此操作。有什么方法可以用 O(n) 时间来解决这个问题，还是不可能（不需要代码）？
作为参考，下面是我试图解决的问题：
问题：
During the school bandmates election, each person has a few preferences for the president and the set of preferences for a person includes him/herself all the time. The "perfect" president is the one who is in the set of preferences of every person and who does not prefer anyone but him/herself. All we want to know is whether such a person exists or not.
- Define a directed graph with the set of candidates as the vertices and a directed edge from vertex a to vertex b if and only if b is in the set of preferences of a.
- There are n people
- We want an algorithm which executes in O(n) time
- We are given the graph described above in the form of an n x n adjacency matrix
我认为如果每个人都投票给“完美总统”，那么 he/she 将有 n 个传入节点，因此对列求和应该给我们 n。如果有比我现在做的更好的方法来解决这个问题，任何提示都将不胜感激，以指导我朝着正确的方向前进。
让我重复一下规则并给它们编号以便于参考：
- 都喜欢自己
- 所有人都喜欢完美的总统（如果有的话）
- 完美总统（如果有的话）不会偏爱任何人
让我们定义邻接矩阵，使得行 i 和列 j 的值在 i 时为 1 对 j 有偏好。所有其他值为 0。
以上三个规则可以根据邻接矩阵重新表述如下：
- 邻接矩阵的主对角线全为 1。
- 如果完美总统是数字i，那么第i列将全为1。
- 如果完美总统是数字 i，那么第 i 行将全为 0，第 i 列除外.
请注意，不能有两个或两个以上的完美总统，因为那样他们就必须互相偏爱（规则 2），这违反了规则 3。
算法：锯齿形阶段
完美总统（如果存在）可以在线性时间内找到，从邻接矩阵（第 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号的人。
证明
给定的是上述zig-zag算法返回的p。
首先我们用反证法证明：
a) 完美总统不能是i小于p.
的人所以让我们假设相反：完美的总统是 i 并且 i < p:
由于我们在第 0 列开始锯齿形阶段并在第 p 列结束，并且由于在此过程中我们不能跳过任何一列，所以有一段时间我们在 i 列中。由于我们没有留在该列中，这一定意味着列 i 的其中一行中有一个零，这要求我们向右移动。但是规则 2 要求如果 i 是一位完美的总统，则 i 列应该只有 1 个值（规则 2）。矛盾！
其次我们用反证法证明：
b)完美总统不可能是i大于p.
的人所以让我们假设相反：完美的总统是 i 并且 i > p:
由于我们在第 0 行开始锯齿形阶段并到达最后一行（参见观察），并且由于在此过程中我们不能跳过一行，所以有一段时间我们在行 我。由于我们没有留在那一行，而是在某个点向下移动（参见观察：我们向下移动移出矩阵），这一定意味着行 i其中一列中有一个 1，它要求我们向下移动。这个 1 不能是对角线上的 1（在 [i,i]），因为我们没有到达第 i 列：i 大于 p 并且算法在列 p 结束。所以它一定是另一个 1，第二个，在行 i.
但是规则 3 要求如果 i 是一位完美的总统，行 i 应该只有一个 1 值，所有其他值为零。矛盾！
这两个矛盾的证明给我们留下了完美总统的其他可能数字，如果有的话，除了 p。
算法：验证阶段
要实际检查人 p 是否确实是一位完美的总统是微不足道的：我们可以检查列 p 是否包含全 1， p 行仅包含 0，i.
列除外时间复杂度
所有这些都可以在线性时间内完成：zig-zag阶段最多需要2n-1次矩阵读取，而2n- 2 更多在最后的验证阶段。因此这是 O(n).