当用邻接矩阵表示时,大多数算法需要的时间都是O(V2)的,但有一些例外
证明:在给定一有向图有向图G的邻接矩阵后,可以在O(V)的时间内确定G中是否含一个“通用的汇(universal sink),即入度为|V|-1,出度为0的顶点。

感觉这题挺有意思,自己想了半天,大概想出了方法,不过有点怀疑正确性,所以GOOGLE了一下

后来发现这还是YAHOO二面的一个题...(P.S.美国雅虎)

图上画画就会发现,这样的图都很有型....

eg.
G:

      1 2 3 4 
   10     1
   2    0 1
   30 0  0   0
   4       1   0

对角线都是0,而是sink的点,横着竖着刚好组成个十字。

while(j<n)
{
      if(G[i,j]=0)
            j++;
      else
            i++;
}
return i;


所以只需要找到十字是在哪个点就成了。这么扫一遍复杂度为O(V)。但有点小问题,如果不是的话,可能返回其它值

eg.
G:
         1 2 3 4
      1 0 0 1 0
      2 1 0 0 0 
      3 1 1 0 1
      4 1 0 1 0
这个的话就会返回2,显然2不是universal sink

所以需要得到答案后再验证一下这个点,横扫竖扫,同样,复杂度也控制在O(V)

顺便,赞一下国外论坛的讨论氛围。
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1195383906

另贴一个网上找的本题的解法
http://www.csie.ntu.edu.tw/~r95122/alg07spr/alg07spr_hw1sol.pdf