当用邻接矩阵表示时，大多数算法需要的时间都是O(V
2)的，但有一些例外
证明：在给定一有向图有向图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