algorithm - 在社交网络中查找 “publisher” 的 O(n) 算法

Question

有人问我如何在社交网络中找到“发布者”。假设(简化的)社交网络在两个用户之间只有“关注”关系，一个不能关注自己。然后我们将“发布者”定义为被所有其他用户关注但不关注任何人的用户。

更具体地说，给定这样一个邻接矩阵格式的社交网络图，比如 NxN bool 矩阵，其中 cell[i,j] 表示用户 i 是否关注用户 j。如何找到发布者。

我能看到的是，至多存在一个发布者。(很容易证明:因为发布者被其他所有人关注，那么其他人至少关注一个用户，所以他们不是发布者)。我确实想出了一个天真的解决方案:首先逐列扫描，如果有一个全部为真的第 j 列(当然除了 cell[j,j])，然后扫描 row[j] 以确保它全部为假。

显然，由于我们扫描了整个矩阵，朴素算法的性能为 O(n^2)。然而，有人告诉我有一个 O(n) 的解决方案。我有点卡在 O(n)。有什么提示吗？

Answer 1

如果您的数据显示为邻接矩阵，那么您可以按如下方式进行。首先检查矩阵中的条目 (1,2)。如果 1 跟随 2 那么 1 不是发布者，如果 1 不跟随 2 那么 2 不是发布者。删除不是发布者的人(1 或 2)，让 X 成为剩余的节点。然后检查矩阵中的条目 (X,3)。同样，您会得到 X 不是发布者或 3 不是发布者。删除不是发布者的人，然后添加节点 4 并重复。在对所有 n 个节点重复此过程后，您将剩下一个发布者候选者。然后您可以检查候选人的行和列以验证它是否是真正的发布者。整个算法的总运行时间为 O(n)，即使邻接矩阵的大小为 n^2。