algorithm - 算法-消除循环

有向图中的泛汇是顶点v，其中v的in度是
|V |-1，出度为0。
我可以通过下面的alg来确定有向图g是否具有通用汇。
注：G表示为邻接矩阵AdjM，并给出了AdjM：

for (i=1 to |V|)
   if (AdjM[i,1] + AdjM[i,2] + AdjM[i,3] + ... + AdjM[i,|V|] == 0)
     && (AdjM[1,i] + AdjM[2,i] + AdjM[3,i] + ... + AdjM[|V|,i] == |V|-1)
    then return i;  // i is a universal sink

我在O（| V |）时间内通过写下
|代码中AdjM[i，]和AdjM[，i]值的V |，从而消除了进行这些求和的内部循环。
有没有一种方法可以做到这一点——在o（v）时间内不显式地解决它
用每个AdjM[i，]和AdjM[，i]作为求和项来编码求和？
必须有更好的方法来使用位智能操作，但我现在看不到。
这是CLRS第530页“图形表示”一节中的问题22.1-6。
提前谢谢。

最佳答案

我认为您可以很容易地构造一个具有一个通用汇的图，并通过在adjm中只更改一个值来将其更改为没有通用汇的图。这意味着必须检查AdjM中的每个值，以确定是否存在通用接收器。
无论你如何巧妙地操作索引和指针，你都不能打败O（| V | ^2）。